末谈背包问题求具体方案

上一篇说了一下背包问题求方案数，下面进行深化一点就是求具体方案了。同上一篇这些问题都是在01背包、多重背包、完全背包基础上演化来的，求具体方案问题会问你一种具体方案（编号序列的字典序最小）或者打印所有具体方案，一般的问题都是问你第一种。若为第二种问法，建议使用C语言的printf进行打印，因为打印所有具体方案，当数据量很大时会有很多输出，使用printf会比cout快一点。

这里继续使用acwing上的题库：12. 背包问题求具体方案 - AcWing题库

这里使用的01背包作为基础比较简单，凡是多说一句，就是对这一题的不尊重，话不多说，直接上代码，代码中有注释，后面也会解释。

#include<iostream>
using namespace std;
int N,V;
int v[1005],w[1005],f[1005][1005];//f[i][j]表示从第i个物品开始到最后一个物品背包容量为j所获得的最大价值
int main(){
    cin>>N>>V;
    for(int i=1;i<=N;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=N;i>=1;i--){//逆序取物，因为f[i][j]定义从i到最后
        for(int j=0;j<=V;j++){
            f[i][j]=f[i+1][j];//先初始化为不选第i个物品
            if(j>=v[i]){//如果背包剩余容量大于物品体积
                f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);//那就寻找最优解，到底是选还是不选所获得总价值更大
            }
        }
    }
    int j=V;
    for(int i=1;i<=N;i++){
        if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){//如果f[i][j]从f[i+1][j-v[i]]+w[i]转移过来，那路径就一定是最优路径
            cout<<i<<" ";
            j-=v[i];//选了就减去背包容量，方便下次寻找
        }
    }
    return 0;
}

题目要求了输出字典序最小，所以尽量靠前去，尽管有不同的方案所获得最大价值一样，但是要考虑字典序最小，所以一定要选前面的，比如选1，3，5和2，3，4所获得的价值一样，但是要选1，3，5，所以后面遍历下标从小到大遍历的。上面说明了如果第一个物品属于最优解的一种，一定要选它，这样问题就转化成了从2~N寻找最优解问题，以此类推。

状态转移：f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]),f[i][j]的上一个状态就是从i+1转移过来的， 因为我们定义从第i个物品到最后一个物品，第i+1个物品到最后一个之间的数量是不是比第i个物品到最后一个物品少。f[i+1][j]是不选第i个物品，f[i+1][j-v[i]]+w[i]是选第i个物品。因为我要在所有f[i][j]当中选择一个最大值，所以前面我管不管的先初始化为不选，往后如果背包容量大于体积，那我再看看是选了这个物品总价值是否增大，如果增大就更新，不增大就保持原来。这样写避免了两重判断最优解，会有两个max，这样只有一个max,其实，好好想一想，我前面先初始化为不选，毫无影响的，后面大于体积那我就走if，不大那就不选呗，那不还是初始化为不选。

最后那一段就是查找最优路径了。首先我先初始为背包容量，面对第i个物品时，若背包剩余容量大于体积并且从上一个状态转移过来，选了第i个物品，那它一定是最优解，并且是字典序是最小的，因为我是正序遍历的。

另外笔者也看到了另一种解法，就是有一个记录路径的二维数组，这样笔者觉得空间复杂度会略上升一点，但也不至于过不了题。虽然第二种解法增加了记录路径的数组，但是笔者还是觉得第一种好理解，力推学会第一种解法即可，下面只展示一下代码。

#include<iostream>
using namespace std;
int N,V;
int v[1005],w[1005],f[1005][1005],p[1005][1005];//f[i][j]表示从第i个物品开始到最后一个物品背包容量为j所获得的最大价值
int main(){
    cin>>N>>V;
    for(int i=1;i<=N;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=N;i>=1;i--){
        for(int j=0;j<=V;j++){
            f[i][j]=f[i+1][j];
            p[i][j]=j;//只记录列--容量即可
            if(j>=v[i]){//这里判断最优
                f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
            }//这里判断选了第i个物品，那就记录路径
            if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){
              p[i][j]=j-v[i];
      }
        }
    }
    int j=V;
    for(int i=1;i<=N;i++){//顺着路径找即可
        if(p[i][j]<j){//选它的容量小于此时背包剩余容量，就是最优解
            cout<<i<<" ";
            j=p[i][j];//更新剩余容量
        }
    }
    return 0;
}

到现在为止，背包九讲问题都更新完了，但是学习不可停止哦，以后我会分享做的一些题，或者再去更新一些知识点和例题，笔者水平有限，一些地方做的不足的地方和需改善的地方大家可以提出来，大家有不明白的地方随时可以私信我，互相学习，大家一起加油！