ABC 15 D - 高橋くんの苦悩 ( 01Knapsack DP )

D: 高橋くんの苦悩 - AtCoder Beginner Contest 015 | AtCoder
ただのナップサック。一回しか使えないという条件があれば、枚挙の順序は逆にして同じものが複数回更新に使われないように注意すること。

#include <bits/stdc++.h>
using namespace std;
const int MAXW = 1e4 + 4;
const int MAXN = 50 + 2;
const int MAXA = 1e3 + 3;
const int MAXB = 100 + 2;
const int INF = 1e9;

int w, n, k;
int a[ MAXN ], b[ MAXN ];

int dp[ MAXN ][ MAXW ]; // number used / width used

void upmax(int &x, int v){
    if( x < v ) x = v;
}

void solve(){
    for(int i = 0; i < n; ++i)
        for(int d = 0; d <= w; ++d)
            dp[ i ][ d ] = -INF;
    dp[ 0 ][ 0 ] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = i; j >= 0; --j)
            for(int d = w - a[ i ]; d >= 0; --d)
                upmax( dp[ j + 1 ][ d + a[ i ] ], dp[ j ][ d ] + b[ i ] );
    int ans = 0;
    for(int i = 0; i <= k; ++i)
        for(int d = 0; d <= w; ++d)
            upmax( ans, dp[ i ][ d ] );
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &w);
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[ i ], &b[ i ]);
    solve();
    return 0;
}