背包问题之求具体方案

题目来源

https://www.acwing.com/problem/content/12/

题目

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

第 i 件物品的体积是 vi，价值是 wi。

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

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

输入格式

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

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

输出格式

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

物品编号范围是 1…N。

数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

输出样例

1 4

本题DP思想

1.
dp数组的定义：dp[i][j]表示考虑了是否选第i个物品以及之后的所有物品之后背包容量不超过j的最优解(价值最大)

2.
状态转移:dp[i][j] = max(dp[i+1][j],dp[i+1][j-v[i]])，状态可以通过(选，不选)来进行转移，它是由上一状态不选第i个物品或者上一状态选第i个物品转移得到.

当dp[i][j] = dp[i+1][j]上一状态且不选第i个物品：这时候的上一状态根据定义就是，考虑第i+1个物品以及之后的所有物品,且背包容量最大不超过j时这个状态,由于未选所以当前状态是直接由上一状态转移
当dp[i][j] = dp[i+1][j-v[i]]+w[i]上一状态选第i个物品：这时候的上一状态根据定义就是，考虑第i+1个物品以及之后的所有物品,且背包容量最大不超过j-v[i]时这个状态(状态转移之后背包体积为j，那么转移之前背包体积肯定就是减去选这个物品的体积啦)，所以当前状态等于上一状态加上当前所选物品的价值
由于求的最优解，所以要从这两种状态转移中选择价值最大的

3.
初始化:由于dp是从最后一个物品开始，所以初始状态是dp[n+1][j]，套上状态定义就是考虑了第n+1个物品及其以后的所以物品且,背包最大体积不超过j的最优解。由于不存在第n+1个物品及其以后的所有物品，所以这时候dp[n+1]x的最优解就是0

4.
本题输出状态转移路径的解释：我们已经有状态转移数组了，我们再通过状态转移数组倒推具体是怎样转移的；可以这样理解，我们记录各种状态转移，并且得到了最优解，现在我们背包里已经装了东西(最优价值),我们枚举每一件物品判断这件物品是否装入了背包里，如果装入了我们就将物品编号输出，然后将该物品从背包中取出，关键就在于怎么判断它是否装入了？这时候就要用到状态转移数组：m-当前最大背包容量，我们判断dp[i]m这个状态是否是dp[i+1]m-v[i]通过装入第i个物品所转移得到的如果是则输出选择的物品序号，并将该物品从背包中取出，取出后背包最大体积为m = m-v[i]，下一次我们又判断dp[i+1][m]这个状态是否是dp[i+1+1][m-v[i+1]]转移得到，代码处还有样例解释

5.
为什么要倒着dp?

题目要求要输出字典序最小，如果1,2,3与1,2,4都能得到最优解，那么应该输出1,2,3.能选3就不能跳过3不选。所以我们应该倒着dp(用下面这个定义考虑，dp[1][V]就表明考虑了第一个及其以后的物品->也就是所有物品后，背包体积不超过V的时刻)然后顺着考虑转移路径，这个定义就是在表明，现在我们背包里已经装了东西(最优价值),我们枚举每一件物品判断这件物品是否装入了背包里，如果装入了我们就将物品编号输出，然后将该物品从背包中取出，怎么表达取出物品？就是背包的最大体积减少!

AC代码

        C
        
      
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 1003;
int dp[MAX][MAX],v[MAX],w[MAX];
/**
 * n-物品总数，V-背包最大容量，dp[MAX][MAX]-状态数组，v[MAX]-存储每个物品体积的数组，w[MAX]-存储每个物品价值的数组
 */
int main(){
    int n,V;    //n-物品总数,V-背包总量
    cin>>n>>V;
    for(int i = 1; i <= V;i++) cin>>v[i]>>w[i];   //将每个物品的体积和价值存储
    
    //for(int x = 0; x <= V; x++) dp[n+1][x] = 0; //状态初始化，全局数组每个初始值都为0所有可以不必初始化
    
    for(int i = n;i>=1;i--){
        for(int j = 0;j<=V;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];
            }
        }
    }
    int m = V;
    for(int i = 1;i<=n;i++){
        //当n<v[i]时肯定该状态是通过没有选i物品转移得到的
        //样例说明，当枚举到第2个物品时，首先看当前背包最大体积是否可能放第2个物品，如果可以，进一步判断当前背包dp[i][m]是否放了第2个物品
        //如果是放入了的情况，那么背包这时候的价值就等于拿出第2个物品后的背包的价值加上物品2的价值(可能是废话)，哈哈哈
        if(m>=v[i] && dp[i][m] == dp[i+1][m-v[i]]+w[i]){
            cout<<i<<" ";
            m-=v[i];
        }
    }
    return 0;
}