背包问题求方案数
背包问题求方案数
01背包模型 f[i][j]
状态表示f(i,j)—集合: 考虑前i个物品,当前体积不超过j的方案
状态表示f(i,j)—属性: Max
状态转移f(i,j):
- 不选第i个物品:f[i-1][j]
- 选第i个物品:f[i-1][j-$v_i$]+$w_i$
路径跟踪 g[i][j]
状态表示g(i,j)—集合: 考虑前 i 个物品,当前已使用体积恰好是 j 的,且价值为最大的方案
—属性: 方案的数量
求出方案的最大值
int res=0;
for(int i=1;i<=m;i++)
res=max(res,f[i]);
如果等于方案的最大值加上该方案的数量
int sum=0;
for(int i=0;i<=m;i++)
if(f[i]==res)
sum=(sum+g[i])%mod;
代码如下
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],g[N];
int n,m;
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--)
{
int maxv=max(f[j],f[j-v]+w);
int s=0;
if(f[j]==maxv) s+=g[j];//不取i的时候
if(f[j-v]+w==maxv) s=(s+g[j-v])%mod;//取i的时候
f[j]=maxv,g[j]=s;
}
}
//求出最大值
int res=0;
for(int i=1;i<=m;i++)
res=max(res,f[i]);
//等于最大值时
int sum=0;
for(int i=0;i<=m;i++)
if(f[i]==res)
sum=(sum+g[i])%mod;
cout<<sum<<endl;
return 0;
}
背包问题求具体方案数量
方法一
因为字典序最小的方案,所以从1到n中,每个物品有3种情况
- (1)只能选,则必须选
- (2)不能选,则必不选
- (3)可选可不选,则必须选
在前面物品能选的情况下优先选择前面的物品
为了满足上述条件,因此需要从第n个物品遍历到第1个物品,求出当前背包的最大总价值f[1][m]
再从第1个物品遍历到第n个物品,其中f[i][j]为当前最优情况,若满足
- (1)f[i][j] == f[i + 1][j],则表示f[i][j]是从f[i + 1][j]状态转移过来的
- (2)f[i][j] == f[i + 1][j - v[i]] + w[i],则表示f[i][j]是从f[i + 1][j - v[i]]状态转移过来的
从而找出字典序最小的路径方案
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=n;i>=1;i--)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i+1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
int j=m;
for(int i=1;i<=n;i++)
if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])
{
cout<<i<<" ";
j-=v[i];
}
return 0;
}
方法二
开一个PII g[i][j]数组来记录,表示first表示(i,j)是由first这个点转移而来,second表示由first转移而来的时候第
first物品是否被选.
g[i][j] = {i + 1, false}:表示(i,j)这个状态是从没选第i + 1个物品转移而来。
g[i][j] = {i + 1, true}:表示(i,j)这个状态是从选第i + 1个物品转移而来
然后边DP边记录即可。
对于输出的过程:首先要判断一下g[i][j].second是否为true如果为true,那么表示是由选择一个物品转移而来,那么当前体积需要跟着变化,那就是减去当前的v,反之如果为false,那么就不必减去当前的v,还有注意这两种情况下i都需要进行转移。
还要注意的就是求解的时候还是要倒序求,因为需要保证字典序最小
int i = 1, j = m;
while (i <= n && j) {
if (g[i][j].second == true) {
int t = i;
cout << i << " ";
i = g[i][j].first;
j -= v[t];
} else {
i = g[i][j].first;
}
}
代码如下
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, bool> PII;
const int N = 1010;
int n, m;
int f[N][N];
int v[N], w[N];
PII g[N][N]; //first表示第几件物品 second表示选没选
vector<int> res;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i + 1][j];
g[i][j] = {i + 1, false};
if (j >= v[i]) {
if (f[i + 1][j - v[i]] + w[i] >= f[i][j]) { //注意这里一定要大于等于,因为为了保证字典序,能选必选
g[i][j] = {i + 1, true};//当前的状态由上一个状态更新过来
f[i][j] = f[i + 1][j - v[i]] + w[i];
}
}
}
}
int i = 1, j = m;
while (i <= n && j) {
if (g[i][j].second == true) {
cout << i << " ";
j -= v[t];//更新体积
i = g[i][j].first;//更新i
} else {
i = g[i][j].first;
}
}
return 0;
}