完全背包问题的具体方案输出

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N],d[N][N],res[N];  //d[i][j] = k记录的是当前第i个物品的在每个j的状态下有k个
int main(){
    cin >> n >>m;
    for(int i = 1; i <= n; i++) cin >>v[i] >>w[i];

    for(int i = 1; i <=n; i++){
        for(int j = 0; j <=m; j++){
            f[i][j] = f[i - 1][j];
            for(int k = 0;k *v[i]<=j; k++){
                if(f[i][j] < f[i-1][j-v[i]*k]+w[i]*k){
                    f[i][j] = f[i-1][j-v[i]*k]+w[i]*k;
                    d[i][j] = k;
                }
            }
        }
    }

    cout << f[n][m]<<endl;
    int tmp = f[n][m];
    int i = n, j = m;
    while(tmp >0 ){
        int k = d[i][j];
        if(k != 0){
            res[i] = k;
            tmp -= k*w[i];
            j -= k*v[i];
            i--;
        }else{
            i--;
        }
    }
    for(int i = 1; i <= n; i++){
        cout<< res[i]<<" ";
    }
    return 0;
}

举个例子：

输入：
3 7
5 4 
3 4
4 5
输出：
9
0 1 1