hdu 2159 FATE（我的第一个二维背包）

FATE

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1914????Accepted Submission(s): 808

#include <iostream>#include <stdio.h>#include <memory.h>using namespace std;int c1[105], c2[105], w[105];int bag[105][105];int n, V, N, S;void _td_bag() //二维背包{ int i, j, k; memset(bag, 0, sizeof(bag)); for(i = 0; i < N; i++) { for(j = c1[i]; j <= V; j++) { for(k = c2[i]; k <= S; k++) { bag[j][k] = max(bag[j][k], bag[j-c1[i]][k-c2[i]] + w[i]); } } }}int main(){ int i, j; bool flag; while(scanf("%d%d%d%d", &n, &V, &N, &S) != EOF) { flag = false; for(i = 0; i < N; i++) { //bag[][]代表经验值 scanf("%d %d", &w[i], &c1[i]); //以忍耐度c1[]为容量1 c2[i] = 1; //以怪数量为容量2 } _td_bag(); for(i = 0; i <= V; i++) { if(bag[i][S] >= n) //刚刚升级 { flag = true; break; } } if(flag) printf("%d\n", V-i); else printf("-1\n"); } return 0;}?