首页 > 代码库 > 背包方案

背包方案

对于一个给定了背包容量、物品费用、物品间相互关系(分组、依赖等)的背包问题,

除了再给定每个物品的价值后求可得到的最大价值外,还可以得到装满背包或将背包装至某一指定容量的方案总数。  

 对于这类改变问法的问题,一般只需将状态转移方程中的max改成sum即可。

例如若每件物品均是01背包中的物品,

转移方程即为f[i][v]=sum{f[i-1][v],f[i-1][v-w[i]]+c[i]},初始条件f[0][0]=1。

【例8】、货币系统

【问题描述】

  给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。样例:设n=3m=10,要求输入和输出的格式如下:

【样例输入】money.in

3  10                                //3种面值组成面值为10的方案

1                                      //面值1

2                                      //面值2

5                                      //面值5

【样例输出】money.out

  10                             //10种方案

 

参考程序

解法一

f[i]表示面值为j的最大方案数,若f[j-k*a[i]]!=0,f[j]+f[j-k*a[i]]1<=i<=n,m>=j>=a[i],1<=k<=j/a[i]

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

using namespace std;

Int n,m;

Int a[1001];

Long long f[10001];

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

   scanf("%d",&a[i]);

    f[0]=1;

for(int i=1;i<=n;i++)

     for(int j=m;j>=a[i];j--)

        for(int k=1;k<=j/a[i ];k++)

        f[i]+=f[i-k*a[i]];

printf("%lld",f[m]);

return 0;

}

 

解法二

f[j]表示面值为j的最大方案数,如果f[j-k*a[i]]!=0,f[j]=f[j-k*a[i]]1<=i<=n,m>=j>=a[i]

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

using namespace std;

int n,m;

int a[1001];

long long f[10001];

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

   scanf("%d",&a[i]);

f[0]=1;

for(int i=1;i<=n;i++)

   for(int j=a[i];j<=m;j++)

      f[j]+=f[j-a[i]];

printf("%lld",f[m]);

return 0;

}

 

背包方案