PKU POJ 1014 Dividing
這道題的分類竟然在“簡單”里面……
確實(shí)沒有找到比較簡單的方法
動(dòng)態(tài)規(guī)劃：
1
#include<stdio.h>
2bool opt[60000];
3int num=0;
4int mid,max;
5int stone[7];
6int input()
7
{
8
scanf("%d%d%d%d%d%d",&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]);
9
if(!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]) {return 1;} //讀到末行
10 num++;
11 printf("Collection #%d:\n",num);
12 mid=0;
13 for(int i=1;i<=6;i++) mid+=stone[i]*i;
14 if (mid % 2 ==1) //明顯的剪枝
15 {
16 printf("Can't be divided.\n\n");
17 return 2;
18
}
19 else mid/=2; //我們的任務(wù)就是求opt
20 return 0;
21
}
22
23void dp()
24{
25 memset(opt,0,60000); //初始化，opt所有成員為false
26 opt[0]=true; //opt[0]顯然是true
27 max=0; //當(dāng)前最大值是0
28
29 for (int i=1;i<=6;i++)
30 {
31 if (stone[i]>0)
32 {
33 for(int j=max;j>=0;j--) // 從當(dāng)前最大值開始往下算
34 if (opt[j]) //找到可行的j
35 {
36 if (opt[mid]) //判斷是否已經(jīng)求出結(jié)果
37 {
38 printf("Can be divided.\n\n");
39 return;
40 }
41 for (int k=1;k<=stone[i];k++) //在剛找到的可行j基礎(chǔ)上加石頭.
42 {
43 if (j+k*i>mid || opt[j+k*i]) break; //如果已經(jīng)大于總價(jià)值的一半mid，或opt[j+k*i]已計(jì)算，跳出循環(huán)
44 opt[j+k*i]=true;
45 }
46 }
47 }
48 max=max+i*stone[i]; //更新當(dāng)前最大值
49 if (max>mid) max=mid; //如果當(dāng)前最大值超過了mid，對(duì)其賦值為mid
50 }
51 printf("Can't be divided.\n\n"); //如果從1到6循環(huán)完一遍后仍然沒有算出opt[mid]，說明無解
52}
53
54int main()
55{
56 while (1)
57 {
58 int t=input();
59 switch (t)
60 {
61 case 1 : return 0; //讀到末行，結(jié)束
62 case 2 : continue; //讀到明顯的剪枝
63 default : dp();
64 }
65 }
66 return 0;
67}
本題是找按價(jià)值均分大理石的方案是否存在，由于分配時(shí)不能破壞大理石，所以有個(gè)顯而易見的剪枝：當(dāng)所有的大理石的總價(jià)值為奇數(shù)時(shí)肯定不能被均分。
把問題轉(zhuǎn)化一下即：由一個(gè)人能否從原大理石堆中取出總價(jià)值為原來一半的大理石
本題的主要算法是動(dòng)態(tài)規(guī)劃
數(shù)組opt代表狀態(tài)：
設(shè)總價(jià)值為V,
當(dāng)opt[k]==true時(shí)，說明，可以有一人獲得價(jià)值k,另外一人獲得價(jià)值V-k的大理石分配方案。反之若opt[k]=false 說明這種分配方案不存在
我們的任務(wù)就是計(jì)算出opt[v/2]是true還是false，即opt[mid]。
顯然有opt[0]==true的方案存在，即一個(gè)人什么都不分，另外一個(gè)人拿走全部的大理石
設(shè)i（1<<6）為石頭的價(jià)值，試想若opt[k]==true，而且在這堆總價(jià)值為k的石頭中有一塊石頭的價(jià)值為i,那么opt[k-i]這種分配方案就是必然存在的了。反過來想，當(dāng)opt[k]==true ，如果能再向k中增加一價(jià)值為i的大理石，則opt[k]==true必然成立
石頭有兩個(gè)屬性，一個(gè)是價(jià)值另一個(gè)是數(shù)量，這里stone[i]代表價(jià)值為i的大理石的數(shù)量，我們根據(jù)其中一個(gè)屬性：價(jià)值 來劃分階段。
即for (int i=1;i<=6;i++)，opt[k]表示狀態(tài)是否存在（這里的狀態(tài)是指能否從原石頭堆中分出價(jià)值為k的新石頭堆）
在初始階段是i=1,初始狀態(tài)是opt[0],max代表目前滿足opt[k]==true這一條件的k的最大值
for(int j=max;j>=0;j--)
//從當(dāng)前最大值opt[開始]，根據(jù)前面提到的opt[j]==true成立則opt[j+i]==true亦成立的理論，在原有狀態(tài)opt[j]==true已存在的條件下加入stone[i]階段的石頭,得到新的狀態(tài)
PS :感謝重慶大學(xué)微軟技術(shù)俱樂部的肖陽同學(xué)
原來這道題果然有更簡單的方法
http://www.blogjava.net/zellux/archive/2007/07/30/133416.html