DP---母函數
先由錢幣兌換問題開始 http://acm.hdu.edu.cn/showproblem.php?pid=1284
Problem Description
在一個國家僅有1分，2分，3分硬幣，將錢N兌換成硬幣有很多種兌法。請你編程序計算出共有多少種兌法。
Input
每行只有一個正整數N，N小于32768。
Output
對應每個輸入，輸出兌換方法數。
這道題有三種解法（參照此博客http://www.cnblogs.com/Findxiaoxun/p/3574907.html）
完全背包的解法很容易想到，模板性質的。
第二種技巧性的就會強一點。這樣想，先只考慮1和3,不是1,就是3,全1的只有一種;每三個1就可以兌換一個3,方法數就有n/3種。再考慮2的情況，全部是2和1的情況，實際上，去掉i個3,就可以變成只含有1和2的情況，而類似的，只含有1和2的情況，可以有(n-3*i)/2種，此時只需要把這些方法數加起來就可以了。
第三種就是母函數了，在此引用下這位大神的博客（http://www.wutianqi.com/?p=596），
Woo講的很好了，尤其是算法歸納的過程，不過個人感覺少了對代碼的分析，這里我毛遂自薦，來講下我的理解: 大家在學習母函數的時候，一定要記住理解這樣一句話：母函數算法其實就是模擬手算多項式乘法。
首先要看Woo的那篇文章，最重要的理解是：
① 、首先對c1初始化，由第一個表達式(1+x+x^2+..x^n)初始化，把質量從0到n的所有砝碼都初始化為1.
② 、 i從2到n遍歷，這里i就是指第i個表達式，上面給出的第二種母函數關系式里，每一個括號括起來的就是一個表達式。
③、j 從0到n遍歷，這里j就是(前面i個表達式累乘的表達式)里第j個變量，(這里感謝一下seagg朋友給我指出的錯誤，大家可以看下留言處的討論)。如(1+x)(1+x^2)(1+x^3)，j先指示的是1和x的系數，i=2執行完之后變為 （1+x+x^2+x^3）(1+x^3)，這時候j應該指示的是合并后的第一個括號的四個變量的系數。
④ 、 k表示的是第j個指數，所以k每次增i（因為第i個表達式的增量是i）。
⑤ 、把c2的值賦給c1,而把c2初始化為0，因為c2每次是從一個表達式中開始的。
Woo這里是根據題目來說的，而且，其實他的代碼里Num那個地方，其實是有兩種的，一般情況下。 來看下母式子： (1+x+x^2+x^3+x^4+..)(1+x^2+x^4++..)(1+x^3+x^6+..) 第一個括號指的是1分的，在拆分第一個括號的之前，1分的能夠構成數m，那么c1[m]=1;如果是有a個1分的，那么1分一直a，c1[a]=1;然后開始拆分第一個括號，就是把第一個括號和第二個括號合并，我們手算多項式乘法，先按括號一的那個1，乘(第二個括號里的內容)，很自然的c2[i]+=c1[i],這里的c2[i]表示的是在這次的循環過程中，中間的結果，這句話理解不了的話，繼續看。然后括號一的第二個元素x，x*(....)=x*1+x*x^2+x*x^4...=x+x^3+x^5...最終，它們會和第一次乘出來的結果同項合并，x^3+x^3=2*x^3,其他值都類似，那么，c2[3]+=c1[1];c1[i]就是保存的之前乘出來的x^i結果的系數，等這一次乘完，c2[i]保存了最終的結果，那就把它的值都轉移到c1里面去，然后c2又空。繼續分解括號。
舉個例子：
3個1分的硬幣，1個2分的，2個3分的。
(1+x+x^2+x^3)(1+x^2)(1+x^3+x^6)
1.初始化：
0 1 2 3 4 5 6 7 8 9
c1:?1 1 1 1 0 0 0 0 0 0
C2全0
2.對第一個括號的1*(1+x^2),(i=2,j=0)得到
0 1 2 3 4 5 6 7 8 9
C2: 1 0 1 0 0 0 0 0 0 0
就是說，原來2個1可以組成2,現在，一個2就能替換，有1種方法。
3. X*(1+x^2) (i=2;j=1)
0 1 2 3 4 5 6 7 8 9
C2: 1 1 1 1 0 0 0 0 0 0
4. X^2*(1+x^2) j=2
0 1 2 3 4 5 6 7 8 9
C2: 1 1 2 1 0 0 0 0 0 0
5. x^3*(1+x^2) j=3
0 1 2 3 4 5 6 7 8 9
C2:1 1 2 2 0 0 0 0 0 0
把c2的值全都轉移到c1里 i=3
剩下的步驟也是如此。
就是模擬手工計算多項式乘法。
Woo的博客介紹的幾道題都挺不錯，現在外面來把這個算法真正的理解運用下：
HDU1711，題意就是說，給價值不同的一些物品，讓你把它們分成和盡可能接近的兩堆。
一種很巧妙的思路是，轉換成完全背包，或者是01背包。因為動態規劃解決的問題一般是最××的問題，最多，最少，最接近，等等。而這個題，可以看成是sum/2空間的背包，讓你用那些物品裝，盡可能裝滿。背包的代碼我先附上，背包專輯我后續我會整理出來。
#include<cstdio>
#include
<algorithm>
#include
<cstring>
using
namespace
std;
const
int
maxn=
5005
;
const
int
maxm=
255555
;
int
n,t,sum;
int
dp[maxm],v[maxn];
int
main(){
while
(scanf(
"
%d
"
,&t)&&t>
0
){
int
a,b;
n
=
0
;sum=
0
;
memset(v,
0
,
sizeof
(v));
for
(
int
i=
0
;i<t;i++
){
scanf(
"
%d%d
"
,&a,&
b);
while
(b--
){
v[n
++]=a;
//
wa
sum+=
a;
}
}
int
sum2=sum/
2
;
memset(dp,
0
,
sizeof
(dp));
for
(
int
i=
0
;i<n;i++
){
for
(
int
j=sum2;j>=v[i];j--
){
dp[j]
=max(dp[j],dp[j-v[i]]+
v[i]);
}
}
//
for(int i=0;i<=sum2;i++)printf("%d ",dp[i]);
int
ans=max(dp[sum2],sum-
dp[sum2]);
printf(
"
%d %d\n
"
,ans,sum-
ans);
}
return
0
;
}
?
再來看母函數的思路。可以這樣想，因為題中對價值的限制為50,也就是說，只有50種值，有50種面值個數不同的硬幣，要你求出，能表示出的最接近總數一半的那個值。轉換為了母函數問題。來看i,j,k 50種面值，1的可以直接先處理，那么i=2 to 50，而j的范圍就是0 to sum，k則是(k=0;k+j<=sum&& k<i*num[i];k+=i)k的限制也很好理解，因為只有num[i]個i面值的硬幣，則多項式最多就能乘到x^(i*num[i])。
#include<cstdio>
#include
<cstring>
#include
<algorithm>
using
namespace
std;
int
c1[
250005
],c2[
250005
];
int
data[
51
];
int
sum;
int
main(){
int
n;
while
(scanf(
"
%d
"
,&n)&&n>
0
){
sum
=
0
;
int
a,b;
memset(data,
0
,
sizeof
(data));
memset(c1,
0
,
sizeof
(c1));
memset(c2,
0
,
sizeof
(c2));
for
(
int
i=
0
;i<n;i++
){
scanf(
"
%d%d
"
,&a,&
b);
data[a]
=
b;
sum
+=a*
b;
}
for
(
int
i=
0
;i<=data[
1
];i++)c1[i]=
1
;
for
(
int
i=
2
;i<=
50
;i++
){
for
(
int
j=
0
;j<=sum;j++
){
for
(
int
k=
0
;j+k<=sum&&k<=i*data[i];k+=
i)
c2[j
+k]+=
c1[j];
}
for
(
int
j=
0
;j<=sum;j++
){
c1[j]
=c2[j];c2[j]=
0
;
}
}
int
x=sum/
2
;
while
(!c1[x]){x--
;}
int
ans=max(x,sum-
x);
printf(
"
%d %d\n
"
,ans,sum-
ans);
}
return
0
;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
