AcWing 12. 背包问题求具体方案

题目传送门

题目要求输出字典序最小的解，假设存在一个包含第\(1\)个物品的最优解，为了确保字典序最小那么我们必然要选第一个。

那么问题就转化成从\(2\)～\(N\)这些物品中找到最优解。

之前的\(f(i,j)\)记录的都是前\(i\)个物品总容量为\(j\)的最优解，现在将\(f(i,j)\)定义为从第\(i\)个元素到最后一个元素总容量为\(j\)的最优解。接下来考虑状态转移：

\(f(i,j)=max(f(i+1,j),f(i+1,j?v[i])+w[i])\)

两种情况:
第一种是不选第\(i\)个物品，那么最优解等同于从第\(i+1\)个物品到最后一个元素总容量为\(j\)的最优解；

第二种是选了第\(i\)个物品，那么最优解等于当前物品的价值\(w[i]\)加上从第\(i+1\)个物品到最后一个元素总容量为\(j?v[i]\)的最优解。

计算完状态表示后，考虑如何的到最小字典序的解。首先\(f(1,m)\)肯定是最大价值，那么我们便开始考虑能否选取第\(1\)个物品呢。

如果\(f(1,m)=f(2,m?v[1])+w[1]\)，说明选取了第\(1\)个物品可以得到最优解。

如果\(f(1,m)=f(2,m)\)，说明不选取第一个物品才能得到最优解。

如果\(f(1,m)=f(2,m)=f(2,m?v[1])+w[1]\)，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

#include 

using namespace std;

//01 背包求具体方案

const int N = 1010;
//二维dp数组，注意：如果题目要求输出具体的方案，就不能使用一维的DP数组，需要用二维的！
int f[N][N];
int v[N];   //第i个物品的体积
int w[N];   //第i个物品的价值
int n;      //n件物品
int m;      //背包容量最大是m

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    //题目要求输出字典序最小的解，倒着进行。因为最终的选择结果需要倒序，这样推导就倒序，再从头到尾来就成了正序
    for (int i = n; i >= 1; i--)
        //01背包在体积循环时的正常方法
        for (int j = 0; j <= m; j++) {
            //不选第i个
            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 = m;
    //f(1,m)是最大价值
    for (int i = 1; i <= n && j; i++) {
        //最后一个，而且还能装的下这个物品
        if (i == n && j >= v[i]) printf("%d", i);//放吧~
        //如果可以选择首先遇到的物品i
        //共三个判断条件，前两个是为了防止第三个越界而设定
        if (i + 1 <= n && j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
            printf("%d ", i), j -= v[i];//剩余容量减小v[i]
    }
    return 0;
}