Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
背包九讲之01背包,二维数组解法,打印选择的背包
/*
* 背包九讲之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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.