题目描述
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？
在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。
输入
第一行输入物品的个数n。
第二行输入物品的重量序列w。(中间有空格）
第三行输入物品的价值序列v。（中间有空格）
第四行输入背包容量c。
输出
第一行输出装入背包的物品。（用0和1表示，中间无空格）
第二行输出最大价值。
样例输入
3
3 4 5
4 5 6
10
样例输出
011
11
背包问题是动态规划的最为基础的问题。初看背包问题，便知道肯定不是用贪心做法，直接选择用动态规划，那就是先分析问题，我们可以得到一个最优子结构，如果选n个物品，容量为c，得到一个最大值，那显然，选n-1个物品，容量为c 或者 c-第n个物品的重量的最大值是之前的一个最大值的子结构。因此我们不但能得到最优子结构，甚至还能知道转移方程该如何构造。dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])，这里的i是一直选到第i个物品，j是容量，那我们最终的答案是什么呢？如果知道这个，就明白了这个递推表达式的含义了，详情看代码。
本题还需要得到一个最优解，一般来说动态规划如果要求得最优解的话，是通过之前我们存放的那个dp表，来找规律的，然后通过回溯法来找到最优解。我已将dp表打印了出来，规律希望大家能找到，代码如下。
#include<iostream>
#define max(x,y) (x)>(y)?(x):(y)
using namespace std;
int f(int **dp,int n,int c,int *w,int *s){
if(dp[n][c]==0){
s[n]=0;
return 0;
}
if(dp[n][c]!=dp[n-1][c]){
s[n]=1;
f(dp,n-1,c-w[n],w,s);
}
else{
s[n]=0;
f(dp,n-1,c,w,s);
}
}
void fun(int n,int *w,int *v,int c,int *s){
int **dp=new int *[n+1];
for (int i=0;i<=n;i++){
dp[i]=new int [c+1];
}
for(int i=0;i<=c;i++){
dp[0][i]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=c;j++){
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=c;j++)
cout<<dp[i][j]<<" ";
cout<<'\n';
}
f(dp,n,c,w,s);//构造最优解
for(int i=1;i<=n;i++){
cout<<s[i];
}
cout<<'\n';
cout<<"背包内最大价值为"<<dp[n][c];
delete []dp;
}
int main(){
int n;
cout<<"请输入n"<<endl;
cin>>n;
int w[n];
int v[n];
cout<<"请分别输入物品重量"<<endl;
for(int i=1;i<=n;i++){
cin>>w[i];
}
cout<<"请分别输入物品价值"<<endl;
for(int i=1;i<=n;i++){
cin>>v[i];
}
int *s=new int [n+1];//存放最优解
int c;
cout<<"请输入背包容量c"<<endl;
cin>>c;
fun(n,w,v,c,s);
}
