背包九讲之01背包，一维（滚动）数组解法

one_zero_pack-2.cpp

/*
 * 背包九讲之01背包 滚动数组
 *  from: http://www.hawstein.com/posts/dp-knapsack.html
 */

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000
#define MAXC 100000

int V[MAXN], W[MAXN];
int d[MAXC+1];

int main() {
    int N, C, w;

    while(cin >> N >> C) {
        memset(V, 0, sizeof(V));
        memset(W, 0, sizeof(W));
        memset(d, 0, sizeof(d));

        for (int i = 0; i < N; i++)
            cin >> V[i] >> W[i];

        // d[i] = max { d[i], d[i-V[j]]+w[j] }
        for (int i = 0; i <= N; i++) {
            for (int j = C; j >= 0; j--) {
                if (i > 0 && j >= V[i-1]) {
                    w = d[j-V[i-1]] + W[i-1];
                    d[j] = d[j] > w ? d[j] : w;
                }
            }
        }

        cout << d[C] << endl;
    }

    return 0;
}