解题思路:
注意事项:
完全背包问题的状态转移方差:s[j]=max(s[j-w]+v,s[j])
具体的max()函数的定义不能一概而论,要具体问题,具体思考
参考代码:
#include <iostream>
using namespace std;
const int MAX=200000;
int minBagC(int *w, int *v, int n, int c)
{
int s[c+1];
for(int j=0;j<=c;j++) s[j]=MAX;
s[0]=0;
for(int i=1;i<=n;i++)
{
int curW=w[i-1],curV=v[i-1];
for(int j=curW;j<=c;j++)
s[j]=min(s[j-curW]+curV,s[j]);
}
return s[c];
}
main()
{
int n=10,w[n],v[n];
for(int i=0;i<n;i++) w[i]=i+1;
for(int i=0;i<n;i++) cin>>v[i];
int c;cin>>c;
cout<<minBagC(w,v,n,c);
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:966 |
【计算直线的交点数】 (C语言代码)浏览:1451 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)from DQM浏览:671 |
1157题解浏览:716 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:834 |
字符串比较 (C语言代码)浏览:685 |
数组输出 (C语言代码)浏览:703 |
整数平均值 (C语言代码)浏览:786 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:956 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:667 |