求背包最大价值的方案数模板题(对于背包容量的不同限制对应不同写法)
该题不是求方案,也不是具体方案,而是求最优解的方案数。
写法1:(背包容量最多为j)
状态表示
f[i][j]
表示从前i物品当中选,最大价值最多为j的所有选法中的最大价值
g[i][j]
表示前i物品当中选,最大价值最多为j的方案数
状态计算
f[ ][ ]:
计算f[i][j]
为普通0 1背包模板,具体参考 AcWing 2. 01背包问题
g[ ][ ]:
初始化所有g[i][0]
为1,表示什么都不选的情况下也有1种方案数
- 如果
f[i][j]
是由f[i - 1][j]
转移过来的,说明最大的方案数也应该是g[i - 1][j]
转移过来的 - 如果
f[i][j]
是由f[i - 1][j - vi]
转移过来的,同理最大方案数也应该是由g[i - 1][j - vi]
转移过来的 - 如果
f[i - 1][j] == f[i - 1][j - vi]
那么g[i][j] += g[i - 1][j] + g[i - 1][j - vi]
朴素版
#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;
}
滚动数组优化版
#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;
}
写法二(背包容量恰好为j)
状态表示
f[i][j]
表示从前i物品当中选,最大价值最多为j的所有选法中的最大价值
g[i][j]
表示前i物品当中选,最大价值最多为j的方案数
状态计算
f[ ][ ]:
初始化f[0][0] = 0
,其余f[0][j]
都为负无穷(因为从0中选,体积是j的方案都是不合法的)
详细说明参考 关于背包容量的三种不同限制:最多、恰好、最少
g[ ][ ]:
g[i][j]
的表示和计算方法与上面一致👆👆👆👆
不同之处
在最后计算完之后,还要重新遍历得到整个f[][]
的最大值res
,最后用res
来重新计算方案数
int res = 0;
for (int j = 0; j <= m; j ++ )
res = max(res,f[n][j]);
int sum = 0;
for (int j = 0; j <= m; j ++ )
if (f[n][j] == res)
sum = (sum + g[n][j]) % mod;
cout << sum << endl;
朴素版
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int f[N][N], g[N][N];
int main()
{
cin >> n >> m;
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
g[0][0] = 1;
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 += g[i - 1][j - v] ;
f[i][j] = maxv, g[i][j] = s % mod;
}
}
int res = 0;
for (int j = 0; j <= m; j ++ )
res = max(res,f[n][j]);
int sum = 0;
for (int j = 0; j <= m; j ++ )
if (f[n][j] == res)
sum = (sum + g[n][j]) % mod;
cout << sum << endl;
return 0;
}
滚动数组优化版
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int f[N], g[N];
int main()
{
cin >> n >> m;
memset(f, -0x3f, sizeof f);
f[0] = 0;
g[0] = 1;
for (int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- )
{
//f[j] = f[j];
//j从大到小遍历:那么j - v是第i - 1层的值,再第i层还没有被更新过
int maxv = max(f[j], f[j - v] + w);
int s = 0;
if (f[j] == maxv) s = g[j];
if (f[j - v] + w == maxv) s += g[j - v] % mod;
f[j] = maxv, g[j] = s % mod;
}
}
/**
背包容量恰好为j的特殊处理:
**/
//还要遍历一遍整个f[j]找出最大值
int res = 0;
for (int j = 0; j <= m; j ++ )
res = max(res,f[j]);
int sum = 0;
//最后再遍历一遍计算f[n][j]寻找最终可以等于res的方案数
for (int j = 0; j <= m; j ++ )
if (f[j] == res)
sum = (sum + g[j]) % mod;
cout << sum << endl;
return 0;
}