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];
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;
}
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.