题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2602
裸的01背包
#include#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int maxn = 1010;int w[maxn], c[maxn], f[maxn];int ans;int n, V;void ZeroOnePack(int cost, int weight){ for(int i = V; i >= cost; i--) { f[i] = max(f[i], f[i-cost] + weight); if(f[i] > ans) ans = f[i]; }}int main(){ //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); while(T--) { ans = 0; memset(f, 0, sizeof(f)); scanf("%d%d", &n, &V); for(int i = 0; i < n; i++) scanf("%d", &w[i]); for(int i = 0; i < n; i++) scanf("%d", &c[i]); for(int i = 0; i < n; i++) ZeroOnePack(c[i], w[i]); printf("%d\n", ans); } return 0;}