解题思路:
注意事项:
参考代码:
#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语言代码)浏览:1291 |
回文数(一) (C语言代码)浏览:751 |
成绩转换 (C语言代码)浏览:1008 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:483 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:544 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:507 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:682 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:531 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:491 |
1054题解浏览:467 |