题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 $1…N$。

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i$, $w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 $1…N$。

数据范围

$ 0<N,V≤1000\\\ 0<v_i,w_i≤1000 $

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

1 4

算法1

01背包模型 时间：$O(n^2)$，空间：$O(n^2)$

该题是01背包问题求方案数的问题。回顾01背包问题的状态转移方程：

$f(i,j) = max(f(i-1,j), f(i-1,j-v))$。

状态$f(i,j)$可能由两个状态转移过来：$f(i-1,j)$或$f(i-1,j-v)$。

因此，只要我们在求解每一个状态$f(i,j)$的时候，把其转移过来的路径记录下来，便能得到了具体方案。实际上，动态规划求具体方案的问题，相当于求最短路问题：求一条从终点到起点的最短路径。

当然，这样了路径有多条，对应于我们的具体方案也有多种。例如，当$f(i-1,j)$和$f(i-1,j-v)$相等的时候，$f(i,j)$可以从以上两个状态转移过来。题目要求我们按字典序输出方案，但我们用之前的状态定义（$f(i,j)$表示仅从前$i$个物品中取，且体积不大于$j$的集合中价值最大）出发，最终求解的结果$f(n,m)$即最短路问题的终点，再往回找，其输出的刚好是与字典序相反的。

为了巧妙的处理这个问题，我们可以逆着求动态规划的解，即状态定义为：$f(i,j)$表示只考虑第$i$个及其后的物品，其总体积之和不大于$j$的价值最大的集合。那么，最终的解就是$f(1,m)$。

此时，依次求解最短路的节点，输出的结果便是以字典序显示的结果。
具体而言，例如当我们考虑第$1$个物品时：
$$ \begin{cases} 1要选, 则选\\\ 1不选, 则不选\\\ 1可选可不选, 则选 \end{cases} $$

综上分析：

状态表示：$f(i,j)$表示只考虑第$i$个及其后的物品，其总体积之和不大于$j$的价值最大的集合。
状态转移方程：$f(i,j) = max(f(i+1,j),f(i+1,j-v_i)+w_i)$

当$f(i,j) == f(i+1,j)$时，表示$f(i,j)$可以从$f(i+1,j)$转移过来，对应的语义就是不取第$i$个物品；当$f(i,j) == f(i+1,j-v_i)+w_i$时，表示$f(i,j)$可以从$f(i+1,j-v_i)$转移过来，对应的语义就是取第$i$个物品，此时要输出$i$。

时间复杂度

状态数$O(n^2)$，计算状态$O(1)$，整体$O(n^2)$。

C++ 代码

#include <iostream>

using namespace std;

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

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }

    int j = m;
    for (int i = 1; i <= n; i++) {
        if ((j >= v[i]) && (f[i][j] == f[i+1][j-v[i]] + w[i])) {
            cout << i << ' ';
            j = j - v[i];
        }
    }

    return 0;
}