第一次做01背包

代码如下：

#include<iostream>
using namespace std;

const int N=1010,V=1010;
int f[N][2];
int dp[N][V];
int main(){
    int n,v;
    scanf("%d %d",&n,&v);
    for(int i=0;i<n;++i){
        scanf("%d %d",&f[i][0],&f[i][1]); //第一个表示体积，第二个表示价值
    }//其实可以用结构体来存体积与价值

    int dp[N][V];//它的物理意义是什么？dp[i][j]表示的是从前i件物品里选择总体积
    //不超过j的物品，并且这些物品的价值最大
    //所以我们对dp[i][j]进行状态划分，可以分为选择第i件物品和不选第i件物品
    //选择第i件物品,意味选择第i件物品，使得总体积不超过j，那么既然选择了第i件，
    //之前的状态就应该是dp[i-1][j - f[i][1] ]
    //状态转移如下：dp[i][j] = dp[i-1][j - f[i][0] ] + f[i][1]
    //不选择第i件物品，意味着从前i-1件物品里选择总体积不超过j的物品，
    //即dp[i][j]=dp[i-1][j]
    for(int i=0;i<n;++i) dp[i][0]=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<=v;++j){//j的物理意义是什么？ 它表示当前背包可用的体积
            if(i>0){
                dp[i][j]=dp[i-1][j];
            }

            if(j-f[i][0]>=0){
                //dp[i][j]=max(dp[i-1][j],dp[i- f[i][2] ][ j - f[i][1] ] + f[i][2]);
                //是否需要
                //i表示第i个物品
                // i - f[i][2]表示的是价值，不能写这句
                //我认为自己是个憨批，f[N][2]中的列只有0，1两个索引，自己居然写出来2
                //j-f[i][1]表示的是体积
                if(i==0){
                    dp[i][j]=f[i][1];
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-f[i][0]]+f[i][1]);
                }

            }

        }
    }
    cout<< dp[n-1][v];
    return 0;
}

过程有点坎坷，花了一个多小时吧，不过收获还是有的。

1.最好不要用二维数组存放物品的体积(质量)以及价值，因为比较难看。不仅外观上难看，调试起来也特别难看，而且还容易写错，就比如我开的是f[N][2],按理说列只有0和1索引，但我写出了2……
2.一定要清楚dp数组的含义，在01背包中，dp[i][j]表示的是从前i件物品中选择总体积不超过j且价值最大的物品。
3.动态规划的核心在于状态方程。在清楚明白动态规划数组的含义后，我们就要进行状态的划分，确定哪个状态能够到达dp[i][j]。在01背包中呢，就是状态方程dp[i][j] = max(dp[i-1][j] , $dp[i-1][j\-v[i]]$ + w[i])。
4.动态规划的一个易错点就是dp数组的初始化(就是因为初始化没处理好才调试了好长时间)。这里要说一点，既然状态转移方程中出现了$i-1$,那么dp数组最好是从1开始，如果从0开始的话，需要特判，巨麻烦。

好了，以上就是我对一些收获。先把朴素做法写上去，优化版本的之后补上。

第二次做01背包问题

代码如下：

#include<iostream>
#include<cstring>
using namespace std;

const int N=1010,V=1010;
int w[N],v[N];

int main(){
    int dp[N][V];
    //memset(dp,0,sizeof dp);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d %d",&v[i],&w[i]);
    }

    // 自己尝试着优化一下
    for(int i=1;i<=n;++i){
        //for(int j=1;j<=v;++j){
        for(int j=v[i];j<=m;++j){
            //if(j>=v[i]){
                dp[i][j]=max(dp[i - 1][j], dp[i-1][j - v[i]] + w[i]);
            //}else dp[i][j]=dp[i-1][j];
        }

        // 思考这样一个问题 如果j<v[i]，那么dp[i][j]等于什么
        // 如果dp[N][V]中所有的元素都初始化为0，那么这么写没有任何错误
        // 否则，会报错。比如dp[3][1],由于j(=1)<v[i](=3),所以我们不进行任何操作
        // 此时dp[3][1]里存放的数据是随机的，可能是0，也可能是其他数
        // 那么后续dp[i][j]可能会用到dp[3][1],那么这个时候由于dp[3][1]的不确定性，就
        //会报错
    }
    cout<<dp[n][m];
    return 0;
}

这次的优化其实只是修改了一下j的范围。第一次做的时候，j的范围是$0 \sim v$,第二次做的时候，j的范围是$v[i] \sim v$。这个改动也导致了dp[i][j]的处理方式的不同。在第一次做的时候，dp[i][j]是分成$ j < v[i] $以及j >= v[i]两种情况来讨论的。在第二次做的时候，由于j>=v[i]，所以我们就不考虑j<v[i]这种情况，自然没有对这种情况下的dp[i][j]进行处理。那我们思考一个问题： 如果j<v[i]，那么dp[i][j]等于什么，如果后面的dp数组用到了这种情况下的信息最终结果还正确吗？

首先说明一点，我把dp数组定义在了main函数内，这就导致了如果不对dp数组初始化，dp数组里面的值是不确定的。
一开始，我利用memset对dp数组初始化，结果未报错；把memset去掉之后，报错，具体原因见代码中的分析。

经过运行，我发现单单把j的范围改掉是不行的，我们还需要对dp数组降维处理。

第3次做01背包

代码如下：

#include<iostream>
#include<cstring>
using namespace std;

const int N=1010,V=1010;
int w[N],v[N];

int main(){
    int dp[V];
    memset(dp,0,sizeof dp);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d %d",&v[i],&w[i]);
    }

    // 自己尝试着优化一下
    for(int i=1;i<=n;++i){
        for(int j=m;j>=v[i];--j){
             dp[j]=max(dp[j], dp[j - v[i]] + w[i]);//此时的dp[j]是上一次循环
             //的dp[j],那么dp[j-v[i]]是否是上一次循环的dp[j-v[i]]
             //就要判断这一层循环的dp[j-v[i]]是否发生改变，如果j是从小到大的话，可能
             //会改变，如果从大到小，就不会改变

        }
    }
    cout<<dp[m];
    return 0;
}