背包问题求方案数

1. \(01\) 背包求恰好装满方案数

f[i][j]: 从前i个物品中选，体积正好为j的方案数
状态转移方程和 \(01\) 背包问题求最大价值是一样的

朴素版

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )   cin >> v[i];
    
    // 从前i个物品中选，体积正好为0的方案数是0
    for(int i = 0; i <= n; i ++ )   f[i][0] = 1;
    
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m; j ++ )
        {
            // 不选
            f[i][j] = f[i - 1][j];
            // 选
            if(j - v[i] >= 0)    f[i][j] += f[i - 1][j - v[i]];
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

优化版

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )   cin >> v[i];
    
    // 从前i个物品中选，体积正好为0的方案数是0
    f[0] = 1;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= v[i]; j -- )
            f[j] += f[j - v[i]];
    
    cout << f[m] << endl;
    
    return 0;
}

2. 完全背包求恰好装满方案数

f[i][j]: 从前i个物品中选，体积正好为j的方案数
但要注意，它的状态转移方程和完全背包求最大价值是不一样的
完全背包求最大价值是 f(i,j) = max(f(i-1,j), f(i-1,j-v)+w, f(i-1,j-2v)+2w,..., f(i-1,j-kv)+kw);
然后通过替换写为 f(i,j) = max(f(i-1,j), f(i,j-v));
但我们这里求方案数不可以写为 f(i,j) = f(i-1,j) + f(i,j-v);
因为求最大价值取得是 \(MAX\)，而求方案数取得是 SUM
也就是说，在这里应为f(i,j) = sum(f(i-1,j), f(i-1,j-v)+w, f(i-1,j-2v)+2w,..., f(i-1,j-kv)+kw);