解题思路:就是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语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:529 |
【亲和数】 (C语言代码)浏览:492 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:534 |
有关字符,字符串的输入输出函数说明浏览:477 |
字符逆序 (C语言代码)浏览:504 |
字符删除 (C语言代码)浏览:713 |
【出圈】 (C++代码)简单循环浏览:627 |
1005答案错误为什么浏览:1975 |
小九九 (C语言代码)浏览:499 |
C语言程序设计教程(第三版)课后习题7.5 (C++代码)浏览:1390 |