暑期dp46道(35)--HDOJ 2159 FATE 背包问题

题目链接：hdoj 2159

背包问题....直接代码

代码：

#include<cstdio> #include<cstring> #include<string> #define debug 0 #define M(a) memset(a,0,sizeof(a)) #define Max(a,b) ((a>b)?a:b) const int maxn = 100 + 5; int c[maxn], w[maxn], ans[maxn][maxn]; int need, v, kind, s; void Do() { for (int i = 1; i <= kind; i++) for (int j = c[i]; j <= v; j++) for (int k = 1; k <= s; k++) { ans[j][k] = Max(ans[j][k], ans[j - c[i]][k - 1] + w[i]); } for (int i = 1; i <= v; i++) for (int j = 1; j <= s; j++) { if (ans[i][j] >= need) { printf("%d\n", v - i);//注意输出 return; } } printf("-1\n"); } int main() { #if debug freopen("in.txt", "r", stdin); #endif//debug int pos, time; while (~scanf("%d%d%d%d", &need, &v, &kind, &s)) { M(ans); for (int i = 1; i <= kind; i++) scanf("%d%d", &w[i], &c[i]); Do(); } return 0; }