解题思路:无限==有限,资源是无穷的,背包是有限的
注意事项:就是多重背包问题
参考代码:
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N=5000;//随需要而定 int n,m; int w[N],v[N],c[N]; int dp[N][N]; int main(){ cin>>m>>n; for(int i=1;i<=n;i++)cin>>w[i]>>v[i]>>c[i];//输入值 for(int i=1;i<=n;i++)if(c[i]==0){ c[i]=m/w[i];//遍历一遍,找到无穷的,求能装下的最大值,这样就是多重背包问题了 } for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=c[i]&&k*w[i]<=j;k++)//数量+占有空间比较 { dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+v[i]*k);//与上一步的结果进行比较k与k+1等 } cout<<dp[n][m];//到最后 return 0; }
0.0分
0 人评分
简单的a+b (C语言代码)浏览:629 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:653 |
C语言训练-素数问题 (C语言代码)浏览:998 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1039 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:775 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:1007 |
剪刀石头布 (C语言代码)浏览:1755 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:902 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1466 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1072 |