背包九讲之01背包，二维数组解法，打印选择的背包

one_zero_pack-1.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], x[MAXN];
int d[MAXN][MAXC];

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

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

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

        /*
         * f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
         */
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= C; j++) {
                d[i][j] = (i == 0) ? 0 : d[i-1][j]; // d[i][j] == d[i-1][j]

                if (i > 0 && j >= V[i-1]) {
                    w = d[i-1][j-V[i-1]] + W[i-1];
                    d[i][j] = (d[i-1][j] > w) ? d[i-1][j] : w;
                }
            }
        }

        for (int i = N, j = C; i > 0; i--) {
            if (d[i][j] > d[i-1][j]) {
                x[i-1] = 1;
                j = j - V[i-1];
            }
        }

        cout << d[N][C] << endl;
        for (int i = 0; i < N; i++)
            cout << x[i] << " ";
        cout << endl;
    }

    return 0;
}