0-1 背包问题（动态规划）

题目描述
给定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);
}