背包问题求具体方案

1.先求一遍背包问题

2.递推判断每个物品是否选了

$ 时间复杂度O(NM)，空间复杂度O(NM) $

求具体方案不能省略表示物品的一维

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 1e3 + 10;

int n, m;
int f[N][N], v[N], w[N];

int main(){
    //读入
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) cin >> v[i] >> w[i];

    //01背包
    for (int i = n ; i >= 1 ; i --){
        for (int j = 0 ; 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]){//选第i个物品
            cout << i << " ";
            j -= v[i];
        }
    }


    return 0;
}