題目連接

題目意思：有單位價(jià)值為1 2 5的三種硬幣，分別給出他們的數(shù)量，求用這些硬幣不能組成的最小的價(jià)值

解題思路：普通的母函數(shù)

普通的母函數(shù)：

　利用母函數(shù)的思想可以解決很多組合問題，下面舉例說明：

　1.口袋中有白球2個(gè)，紅球3個(gè)，黃球1個(gè)，從袋中摸出3個(gè)球有幾種取法？

　 ? 和上面描述的例子類似，我們可以用次數(shù)代表球的個(gè)數(shù)，多項(xiàng)式的每一項(xiàng)前面的系數(shù)代表取法的種樹。

　　可以很容易地寫出下面這個(gè)式子：

　　（1+x+x²）（1+x+x²+x³）（1+x）

?　　（1+x+x²）表示有白球2個(gè)，1（1可以看做是x的0次方）表示白球不取，x代表取1個(gè)白球，x2代表取2個(gè)白球，即用x的次數(shù)表示取球的個(gè)數(shù)，后面的也是類似。那么這個(gè)多項(xiàng)式的乘積就把所有的情況都表示出來了，對(duì)于最終乘積的每一項(xiàng)a_nxⁿ，表示取n個(gè)球有a_n種取法。

?

? ? 2.有若干個(gè)1克，2克，5克的砝碼，要稱出20克的重量，有多少種稱法？

　　這里不限制砝碼的個(gè)數(shù)，無所謂，照樣寫出母函數(shù)：

　　（1+x+x²+x³+......x^k+....）（1+x²+x⁴+x⁶......+x²ⁿ+......）（1+x⁵+x¹⁰+......x5^m+......）

　　因?yàn)橐Q出20克，所以只需要找找到結(jié)果中次數(shù)為20 的那一項(xiàng)就可以得到結(jié)果。

? ? 3.同樣對(duì)于正數(shù)劃分也可以解決，比如有整數(shù)20，劃分成1，2，5，有多少種劃分方法？

　　解法和2的類似。

? ? ?還有一類題目和這類似，有n個(gè)球放到m個(gè)盒子中，有多少種不同的放法？

? ? （1+x+x2+x3+...xk+...）（1+x+x2+x3+...xk+...）（1+x+x2+x3+...xk+...）總共有m項(xiàng)，然后找出乘積中次數(shù)為n的那一項(xiàng)系數(shù)。

代碼實(shí)現(xiàn)：

模擬多項(xiàng)式的乘積過程，c[i]表示次數(shù)為i的系數(shù)，成tempc[]數(shù)組是一個(gè)暫存數(shù)組

該題的母函數(shù)不難得出是（1+x+x²+x³+......x^k+....）（1+x²+x⁴+x⁶......+x²ⁿ+......）（1+x⁵+x¹⁰+......x5^m+......）

對(duì)于單位價(jià)值為1的硬幣，不去次數(shù)為0，取一個(gè)次數(shù)為1，取兩個(gè)次數(shù)為2.。。。。。

對(duì)于單位價(jià)值為2的硬幣，不去次數(shù)為0，取一個(gè)次數(shù)為2，取兩個(gè)次數(shù)為4.。。。。。

對(duì)于單位價(jià)值為5的硬幣，不去次數(shù)為0，取一個(gè)次數(shù)為5，取兩個(gè)次數(shù)為10.。。。。。

普通母函數(shù)的精髓就是將組合問題通過次數(shù)及系數(shù)來表示在某次組合中的選擇是怎樣的，如分別選擇多少個(gè)什么種類的東西

c[]數(shù)組初始化為第一個(gè)多項(xiàng)式乘積因子（1+x+x²+x³+......x^k+....）的相應(yīng)次數(shù)的系數(shù)

tempc[]數(shù)組暫存多項(xiàng)式乘積因子（1+x+x²+x³+......x^k+....）與多項(xiàng)式乘積因子（1+x²+x⁴+x⁶......+x²ⁿ+......）相乘后相應(yīng)的次數(shù)的系數(shù)，并賦給c[]數(shù)組。

注意：此時(shí)c[]數(shù)組存儲(chǔ)的是多項(xiàng)式乘積因子（1+x+x²+x³+......x^k+....）與多項(xiàng)式乘積因子（1+x²+x⁴+x⁶......+x²ⁿ+......）相乘后相應(yīng)的次數(shù)的系數(shù)。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 int main() 8 { 9 int cent[3]={1,2,5}; 10 int i,j,k,num[3],c[8005],tempc[8005]; 11 while(~scanf("%d%d%d",&num[0],&num[1],&num[2])) 12 { 13 if(num[0]==0&&num[1]==0&&num[2]==0)break; 14 int max=num[0]+num[1]*2+num[2]*5; 15 memset(c,0,sizeof(c)); 16 memset(tempc,0,sizeof(tempc)); 17 for(i=0;i<=num[0]*cent[0];i+=cent[0]) 18 c[i]=1; 19 for(i=1;i<3;i++) 20 { 21 for(j=0;j<=max;j++) 22 for(k=0;k+j<=max&&k<=cent[i]*num[i];k+=cent[i]) 23 tempc[k+j]+=c[j]; 24 for(j=0;j<=max;j++) 25 { 26 c[j]=tempc[j]; 27 tempc[j]=0; 28 } 29 } 30 for(i=0;i<=max;i++) 31 { 32 if(c[i]==0)break; 33 } 34 printf("%d\n",i); 35 } 36 return 0; 37 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/WHLdbk/p/6361362.html

總結(jié)

以上是生活随笔為你收集整理的hdu1085Holding Bin-Laden Captive!组合问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。