背包记录路径

主要就是i - - 时有没有else的区别
01背包没有else
完全背包有else

    int i = n, j = m;
    while(i > 0 && j > 0)
    {
        if(path[i][j] == 1)
        {
            cout << w[i] << endl;
            j -= v[i];
        }
        else i -- ;
    }

01背包

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

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 = m; j >= v[i]; j -- )
        {
            if(f[j] < f[j - v[i]] + w[i])
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
                path[i] = 1;
            }
        }   
    cout << f[m] << endl;

    int i = n, j = m;
    while(i > 0 && j > 0)
    {
        if(path[i][j])
        {
            cout << w[i] << endl;
            j -= v[i];
        }
        i -- ;
    }

    return 0;
}

完全背包

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

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 = v[i]; j <= m; j ++ )
            if(f[j] < f[j - v[i]] + w[i])
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
                path[i][j] = 1;
            }

    cout << f[m] << endl;

    int i = n, j = m;
    while(i > 0 && j > 0)
    {
        if(path[i][j] == 1)
        {
            cout << w[i] << endl;
            j -= v[i];
        }
        else i -- ;
    }

    return 0;
}