求最大价值方案数

该题不是求方案，也不是具体方案，而是求最优解的方案数。

注意：图中的状态表示和计算省略了一维，实际上本质上应该是二维的g[i][j]表示从前i件物品选，体积为j 的具体方案数。

$ 时间复杂度O(NM),空间复杂度O(M) $

参考文献

算法提高课

AC代码

#include<iostream>
using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

int f[N][N], g[N][N];
int n, m;

int main()
{
    cin >> n >> m;

    //初始化g
    for (int i = 0 ; i <= m ; i ++) g[0][i] = 1;

    //背包dp
    for(int i = 1; i <= n; i ++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = 0; j <= m; j ++)
        {
           int maxv = f[i - 1][j];
           if (j >= v) maxv = max(maxv, f[i - 1][j - v] + w);
           int s = 0;
           if (maxv == f[i - 1][j]) s = g[i - 1][j];
           if (j >= v && maxv == f[i - 1][j - v] + w) s = (s + g[i - 1][j - v]) % mod;
           f[i][j] = maxv, g[i][j] = s;
        }
    }


    printf("%d", g[n][m]);
    return 0;
}

一维空间优化

g数组也只用到了上一层的状态，所以只用一维数组即可。

注意：如果要用一维，两个数组都要一维，要保持一致

#include<iostream>
using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

int f[N], g[N];
int n, m;

int main()
{
    cin >> n >> m;

    //初始化g
    for (int i = 0 ; i <= m ; i ++) g[i] = 1;

    //背包dp
    for(int i = 1; i <= n; i ++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = m ; j >= v ; j --)
        {
           int maxv = max(f[j], f[j - v] + w);
           int s = 0;
           if (maxv == f[j]) s = g[j];
           if (maxv == f[j - v] + w) s = (s + g[j - v]) % mod;
           f[j] = maxv, g[j] = s;
        }
    }


    printf("%d", g[m]);
    return 0;
}