解题思路:
注意事项:
参考代码:
#include<iostream> using namespace std; int N;//物品个数 int C;//背包容量 int v[1000],w[10000];//物品价值、重量 int dp[1000][10000]; void traceback(); int main() { cin>>N>>C; for(int i=1;i<=N;i++) cin>>w[i]>>v[i]; for(int i=1;i<=N;i++) //从一号物品进行遍历 for(int j=0;j<=C;j++) //j表示背包可用空间 { if(j<w[i]) //如果容量不够,自动继承装入上一个物品时的价值 dp[i][j]=dp[i-1][j]; else //容量够,比较装入和不装入的价值,选择较大的 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } cout<<dp[N][C]; //cout<<endl; //traceback(); } //查看装入物品的编号,本题用不到,忽略! void traceback() { int temp=C; int x[N+1]; for(int i=N;i>=1;i--) if(dp[i][temp]==dp[i-1][temp]) x[i]=0; else { temp-=w[i]; x[i]=1; } for(int i=1;i<=N;i++) if(x[i]==1) cout<<i<<" "; cout<<endl; return; }
0.0分
0 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:629 |
字符串输入输出函数 (Java代码)浏览:1438 |
校门外的树 (C语言代码)浏览:693 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:637 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:467 |
有关字符,字符串的输入输出函数说明浏览:479 |
printf基础练习2 (C语言代码)浏览:503 |
字符逆序 (C语言代码)求大神指出错处,运行结果尝试了也与要求一样,但就是说结果错误,不知错在哪里浏览:436 |
循环链表与单个结点删除浏览:1102 |
printf基础练习2 (C语言代码)浏览:598 |