解题思路:
注意事项:
参考代码:
#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 人评分
【数组的距离】 (C语言代码)浏览:608 |
十->二进制转换 (C语言代码)浏览:1410 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:1072 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:2468 |
程序员的表白 (C语言代码)浏览:667 |
Wu-求圆的面积 (C++代码)浏览:1896 |
水仙花 (C语言代码)浏览:1054 |
字符逆序 (C语言代码)浏览:621 |
Pascal三角 (C语言代码)浏览:653 |
拆分位数 (C语言代码)浏览:522 |