貨币系統 背包問題的方案總數

1273：【例9.17】貨币系統

【題目描述】

給你一個n種面值的貨币系統，求組成面值為m的貨币有多少種方案。

【輸入】

第一行為n和m。

【輸出】

一行，方案數。

【輸入樣例】

3 10 //3種面值組成面值為10的方案

1 //面值1

2 //面值2

5 //面值5

【輸出樣例】

10 //有10種方案

思路：

這是一種求方案總數的背包問題。其實在之前的背包問題的技巧總結中，對于這一類的問題已經進行總結了。現在再來複習一下。

題型：對于一個給定了背包容量、物品費用、物品間互相關系（分組、依賴等）的背包問題，除了再給定每個物品的價值後求可得到的最大價值外，還可以得到裝滿背包或将背包裝至某一指定容量的方案數。

對于這類改變問法的問題，一般隻需将狀态轉移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，轉移方程即為f[i][v] = sum { f[i-1][v] , f[i-1][v-w[i]] + c[i] }，初始條件為f[0][0] = 1。

然後判斷是哪種背包就采用哪種背包的方法。可以根據題目進行細節（初始化等）的變換。

本題分析：

二維數組中變成了一個記錄求和的數組，且本題中是求恰好組成的，是以對于第一個值f[0][0]=1，所對于其他的值可以指派為0.(因為是求方案數，詳情看之前講解的背包問題規律小總結)此題是有各種面值的物品可以無限次使用，是以屬于完全背包，是以可以采用完全背包的方法。

代碼 寫法1（推薦）：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
//背包問題 求方案總數
//一般求恰好的時候，如果是普通背包問題 将j=0時初始化為0，其他的可以無限小。
//但是如果是求方案種數的話 ，将j=0時，方案初始化為1，其他初始化為0。因為最終不是0的話就不是恰好。 
//代價：面值   價值：方案數 
int main()
{
 int n,m;
 cin>>n>>m; 
 long long int a[10001];//壓縮的記錄數組 
 memset(a,0,sizeof(a));
 int w[1001];//代價，記錄面值  
 for(int i=1;i<=n;i++)
 {
  cin>>w[i];
  } 
 a[0]=1;//初始化 恰好的時候為1
 for(int i=1;i<=n;i++)
 {
  for(int j=w[i];j<=m;j++)//完全背包思想 用從後向前周遊 
  {
   a[j]=a[j]+a[j-w[i]];//不加這個物體上次求的恰好的方案數+加上這個物體的恰好的方案數 
  }
  /*for(int j=0;j<=m;j++)
   cout<<a[j]<<' ';
  cout<<endl; */
 }
 
 cout<<a[m]; 
 return 0;
}
           

代碼 寫法二：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
//背包問題 求方案總數
//一般求恰好的時候，如果是普通背包問題 将j=0時初始化為0，其他的可以無限小。
//但是如果是求方案種數的話 ，将j=0時，方案初始化為1，其他初始化為0。因為最終不是0的話就不是恰好。 
//代價：面值   價值：方案數 
int main()
{
 int n,m;
 cin>>n>>m; 
 long long int a[10001];//壓縮的記錄數組 
 memset(a,0,sizeof(a));
 int w[1001];//代價，記錄面值  
 for(int i=1;i<=n;i++)
 {
  cin>>w[i];
  } 
 a[0]=1;//初始化 恰好的時候為1
 
 for(int i=1;i<=n;i++)
 {
  for(int j=m;j>=w[i];j--)//完全背包思想 涉及到累加，是以從後向前無後效性周遊，采用三層for循環方法 
  {
   for(int k=1;j-k*w[i]>=0;k++) 
    a[j]=a[j]+a[j-k*w[i]];//不加這個物體上次求的恰好的方案數+加上這個物體的恰好的方案數 
  }
  /*for(int j=0;j<=m;j++)
   cout<<a[j]<<' ';
  cout<<endl; */
 }
 
 cout<<a[m]; 
 return 0;
}