题目描述
背包问题求方案数，注意要点
1. fij要设成”恰好”
2. 注意”恰好”的初始化方法
3. 由于是”恰好”，又要取max，所以要初始化为负无穷
样例
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010,M=1e9+7;
//fj表示体积"恰好"为j的方案
//g[i][j]表示fij取最大值的方案数
int f[N],g[N];
int v[N],w[N];
int main()
{
//由于是"恰好"，又要取max，所以要初始化为负无穷
memset(f,-0x3f,sizeof f);
int n,m;
cin>>n>>m;
f[0]=0;
g[0]=1;
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--)
{
int maxv=max(f[j],f[j-v[i]]+w[i]);
int cnt=0;
if(maxv==f[j]) cnt+=g[j];
if(maxv==f[j-v[i]]+w[i]) cnt+=g[j-v[i]];
g[j]=cnt%M;
f[j]=maxv;
}
}
int res=0;
for(int i=1;i<=m;i++)
res=max(res,f[i]);
int cnt=0;
for(int i=0;i<=m;i++)
{
if(f[i]==res)
cnt=(cnt+g[i])%M;
}
cout<<cnt;
return 0;
}
二刷发现，这题用“恰好”的思路和“不超过”的思路都可以做，下面把这两种做法再写一遍
不超过：
如果装新物品的方案总价值更大，那么用 f[j−v]+w 来更新 f[j]，用g[j−v] 更新 g[j]
如果总价值相等，那么最大价值的方案数就多了 g[j−v]种
如果装性物品的方案总价值没有不装大，则方案不改变
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010;
const int mod=1e9+7;
int f[N];
int g[N];
int w[N],v[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
//体积不超过j时的最优方案数 为1（一个都不拿的一种）
for(int i=0;i<=m;i++)
{
g[i]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
if(f[j]<f[j-v[i]]+w[i])
{
g[j]=g[j-v[i]];
}
else if(f[j]==f[j-v[i]]+w[i])
{
g[j]=(g[j]+g[j-v[i]])%mod;
}
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<g[m];
return 0;
}
恰好：
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010;
const int mod=1e9+7;
int f[N];
int g[N];
int w[N],v[N];
int main()
{
memset(f,-0x3f,sizeof f);
f[0]=0,g[0]=1;
int n,m;
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--)
{
int maxv=max(f[j],f[j-v[i]]+w[i]);
int cnt=0;
if(maxv==f[j]) cnt+=g[j];
if(maxv==f[j-v[i]]+w[i]) cnt+=g[j-v[i]];
g[j]=cnt%mod;
f[j]=maxv;
}
}
int res=0;
for(int i=1;i<=m;i++)
{
res=max(res,f[i]);
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(f[i]==res)
ans=(ans+g[i])%mod;
}
cout<<ans;
return 0;
}
2023/11/28
复习了很久，写出来了
和之前求方案数的题目不一样：
1021 货币系统
1023 买书
该题是求“满足最大价值”的方案数，而不是求“把物品装入背包”的方案数， 所以求方案数的过程有所区别：
要在循环内进行判断：
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
if(f[j]<f[j-v[i]]+w[i])
{
g[j]=g[j-v[i]];
}
else if(f[j]==f[j-v[i]]+w[i])
{
g[j]=(g[j]+g[j-v[i]])%mod;
}
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
// 而不是每种情况都加上
for(int i=1;i<=n;i++)
{
for(int j=0;j<=maxa;j++)
{
f[i][j] = f[i-1][j];
if(j >= a[i])
{
f[i][j] += f[i][j-a[i]];
}
}
}
此外，该题有两种解法，根据状态转移方程的定义：
1. 不超过：
fij: 从前i个物品中选，体积”不超过”j的最大价值
gij: 从前i个物品中选，体积”不超过”j的最优解的方案数
在这种定义下， fij是我们熟悉的初始化及更新方式：fij就用01背包的方式去更新.
gij的初始化是重点：
参考 1023. 买书中，“不超过”方案数的求法，gij应该这样初始化：
// 这里g要用"不超过"cnt类的初始化方式
// 且注意要从0开始初始化，不能从1开始
for(int i=0;i<=m;i++)
{
g[0][i] = 1;
}
整体代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010;
const int mod=1e9+7;
// fij: 从前i个物品中选，体积"不超过"j的最大价值
int f[N][N];
// g[i][j]: 从前i个物品中选，体积"不超过"j的最优解的方案数
int g[N][N];
int n,m;
int v[N],w[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
// 这里g要用"不超过"cnt类的初始化方式
// 且注意要从0开始初始化，不能从1开始
for(int i=0;i<=m;i++)
{
g[0][i] = 1;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
// 不取第i个物品
f[i][j] = f[i-1][j];
g[i][j] = g[i-1][j] % mod;
if(j>=v[i])
{
// 如果取第i个物品为最优解
if(f[i][j] < f[i-1][j-v[i]]+w[i])
{
g[i][j] = g[i-1][j-v[i]] % mod;
}
// 如果取第i个物品和不取，结果相等，则方案数要加上
else if(f[i][j] == f[i-1][j-v[i]]+w[i])
{
g[i][j] = (g[i][j] + g[i-1][j-v[i]]) % mod;
}
f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
}
}
}
cout<<g[n][m];
return 0;
}
- “恰好”
如果按照”恰好”定义：
fij: 从前i个物品中选，体积”恰好”为j的最大价值
gij: 从前i个物品中选，体积”恰好”为j的最优解的方案数
此时gij是我们熟悉的初始化及更新方式: 按照整数划分、货币系统等”恰好”求方案数的方式初始
// "恰好"求方案数的初始化
g[0][0] = 1;
重点是fij的初始化：
要参考 1020. 潜水员，总结的”恰好”背包的初始化方式：
// "恰好"求方案数的初始化
g[0][0] = 1;
f0初始化为0，其余为正无穷 (或负无穷， 根据求最大值还是最小值判断，总之其余要初始化为一个”不合法”的值)。
memset(f,-0x3f,sizeof f);
f[0][0]=0;
此外，若定义为”恰好”
还需要对最优解进行判断，因为最优解不一定是把体积恰好用完:
int res=0;
for(int i=1;i<=m;i++)
{
res=max(res,f[n][i]);
}
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010;
const int mod=1e9+7;
// fij: 从前i个物品中选，体积"恰好"为j的最大价值
int f[N][N];
// g[i][j]: 从前i个物品中选，体积"恰好"为j的最优解的方案数
int g[N][N];
int n,m;
int v[N],w[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
// "恰好"求最优解的初始化
memset(f,-0x3f,sizeof f);
f[0][0]=0;
// "恰好"求方案数的初始化
g[0][0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
// 不取第i个物品
f[i][j] = f[i-1][j];
g[i][j] = g[i-1][j] % mod;
if(j>=v[i])
{
// 如果取第i个物品为最优解
if(f[i][j] < f[i-1][j-v[i]]+w[i])
{
g[i][j] = g[i-1][j-v[i]] % mod;
}
// 如果取第i个物品和不取，结果相等，则方案数要加上
else if(f[i][j] == f[i-1][j-v[i]]+w[i])
{
g[i][j] = (g[i][j] + g[i-1][j-v[i]]) % mod;
}
f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
}
}
}
int res=0;
for(int i=1;i<=m;i++)
{
res=max(res,f[n][i]);
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(f[n][i]==res)
ans=(ans+g[n][i])%mod;
}
cout<<max(ans, 1);
return 0;
}
总结：背包问题的”恰好”和”不超过”
在求最优解，即最大价值时，”恰好”和”不超过”的区别在于；fij的初始化：
-
恰好：且在循环内要严格保证 体积>=0
memset(f,-0x3f,sizeof f);
f[0][0]=0; -
不超过 ：全初始化为0， 且在循环内要严格保证 体积>=0
在求方案数时，”恰好”和不超过的区别也在于初始化：
见上述 “完全背包的cnt类 总结”
最常见的是：
- 求不超过的最优解： 背包问题
- 恰好的方案数：整数划分，货币系统
兄弟写得真好！
棒棒哒！