解题思路:就是01背包,多重背包,和无限背包合起来,加个判断条件就好了
注意事项: 1.这里使用普通的dp数组,方便初学者理解. 加上这道题普通的dp数组也可以过,就不再优化了
2.N物品数量有大于三十的情况,题目有误.所以数组要开大点.
参考代码:
#include<bits/stdc++.h> using namespace std; int M,N; int dp[305][2005]; int i,j,k; int W[305],C[305],P[305]; int main() { scanf("%d %d",&M,&N); getchar(); for(i = 1; i <= N; i++) { scanf("%d %d %d",&W[i],&C[i],&P[i]); getchar(); } for(i = 1; i <= N; i++) { for(j = 1; j <= M; j++) { if(P[i] == 0)//无限背包 { for(k = 0;(j - k*W[i]) >= 0 ; k++) { dp[i][j] = max(dp[i][j],dp[i-1][j-k*W[i]]+k*C[i]); } } else//01背包 与 多重背包 { for(k = 0; k <= P[i] && (j- k*W[i] >= 0); k++) { dp[i][j] = max(dp[i-1][j- k*W[i]] + k*C[i],dp[i][j]); } } } } cout << dp[N][M]; return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题7.4 (Java代码)浏览:843 |
C语言程序设计教程(第三版)课后习题8.3 (Java代码)浏览:1374 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:495 |
C语言程序设计教程(第三版)课后习题1.6 (C++代码)浏览:902 |
C二级辅导-阶乘数列 (C语言代码)浏览:692 |
C语言训练-数字母 (C语言代码)浏览:649 |
用筛法求之N内的素数。 (C++代码)浏览:693 |
1017题解浏览:605 |
罗列完美数 (C语言代码)浏览:491 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:707 |