完全背包问题。容量为10的背包,有5种物品,每种物品数量无限,其重量分别为5,4,3.2,1,其价值分别为1,2,3,4,5。设计算法,实现背包内物品价值最大。代码如下(输出50):
#include<iostream>#include<algorithm>
using namespace std;
int main()
int total weight=10;
int w[6]-(0,5,4,3,2,1};
int v[6]=(0,1,2;3,4,5};
int dp[11]-(;
for(int i=l;i<=for(int j=w[i];j<=;う++)dp[j]=
<<endl;
cout<<
return 0i
1处应填
0
5
10
15
2处应填
5
6
10
15
3处应填
5
6
10
15
4处应填
dp[j]+v[i]
dp[j-w[i]]+v[i]
min(dp[j],dp[j-w[i]]+v
max(dp[j],dp[j-w[i]]+v[i])
5处应填
v[10]
dp[ 10]
w[10]
total_weight
发表评论