http://acm.hdu.edu.cn/showproblem.php?pid=2159
二维完全背包,限定因素是容量和物品总个数,内层循环顺序,
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int dp[110][110]; int main() { int n,m,k,s; int c[110],w[110]; while(~scanf("%d %d %d %d",&n,&m,&k,&s)) { for(int i = 1; i <= k; i++) scanf("%d %d",&w[i],&c[i]); for(int i = 0; i <= m; i++) { for(int j = 0; j <= s; j++) { if(j == 0) dp[i][j] = 0; else dp[i][j] = -INF; } } for(int i = 1; i <= k; i++) { for(int j = c[i]; j <= m; j++) { for(int g = 1; g <= s; g++) { dp[j][g] = max(dp[j][g], dp[j-c[i]][g-1]+w[i]); } } } int f = 0; for(int i = 0; i <= m; i++) { for(int j = 0; j <= s; j++) { if(dp[i][j] >= n) { printf("%d\n",m-i); f = 1; break; } } if(f == 1) break; } if(!f) printf("-1\n"); } return 0; }