AcWing 11. 背包问题求方案数
原题链接
中等
作者:
长夜未央
,
2022-07-29 14:59:24
,
所有人可见
,
阅读 144
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int n,m;
int f[N]; //f[i]表示背包容量为i时能装入物品的最大价值
int c[N]; //c[i]表示背包容量为i时最优选法的方案数
int main()
{
scanf("%d%d",&n,&m);
//体积从0到m,初始化方案数为1 特别注意c[0]也要是1
//因为体积为0它也是一种方案,可以立即为"把某个物品放入容量为0的背包时的最大价值是0"
//而这也是一种合法的方案
for(int i=0;i<=m;i++)
c[i]=1;
//跑一边01背包
for(int i=1;i<=n;i++)
{
int v,w;
scanf("%d%d",&v,&w);
for(int j=m;j>=v;j--)
{
//容量从j-v到j,只是多装入了一件物品,并没有改变方案数
if(f[j-v]+w>f[j])
{
f[j]=f[j-v]+w;
c[j]=c[j-v];
}
//不装入新物品,容量j已有的方案数为c[j]
//装入新物品,容量j对应的方案数为c[j-v]
//就比如题目给定5 5 然后有{体积,价值}为【{5,8}】、【{2,4}和{3,4}】、【{4,8}】
//可以发现最大价值都为8,但是是三种不同的方案
else if(f[j-v]+w==f[j])
{
c[j]=(c[j]+c[j-v])%mod;
}
}
}
printf("%d\n",c[m]);
return 0;
}