Onway

我是一只菜菜菜菜鳥...

posts - 61, comments - 56, trackbacks - 0, articles - 34

pku 1014 Dividing 多重背包

Posted on 2010-08-04 23:26 Onway 閱讀(299) 評論(0) 編輯收藏引用所屬分類: 傷不起的ACM

pku 1014 Dividing

這個題目跟3211 Washing Clothes做法非常相似，雖然3211是0-1背包，1014是多重背包。思路都是將總價值的一半作為背包容量，然后進行背包策略就行了。

用多重背包的個數標記，時間為O(N*M),一次AC。

然后用二進制物品壓縮，數組開小了，居然報WA，暈死。

#include <iostream>
2

using namespace std;
3

const int MAX=60000;
4

bool sgn[MAX+1];
5

int cnt[MAX+1];
6

int data[7];
7

int main()
8

{
9

int cas=0;
10

while(cin>>data[1]>>data[2]>>data[3]>>data[4]>>
11

data[5]>>data[6])
12

{
13

int i,j,n=6,sum=0;
14

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

if(data[i]!=0)
16

break;
17

if(i>n) break;
18

++cas;
20

memset(sgn,0,sizeof(sgn));
22

sgn[0]=1;
23

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

{
25

memset(cnt,0,sizeof(cnt));
26

for(j=i;j<=MAX;++j)
27

if(!sgn[j]&&sgn[j-i]&&cnt[j-i]<data[i])
28

{
29

cnt[j]=cnt[j-i]+1;
30

sgn[j]=1;
31

}
32

}
33

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

sum+=data[i]*i;
36

if(sum%2||!sgn[sum/2])
37

{
38

cout<<"Collection #"<<cas<<":"<<endl;
39

cout<<"Can't be divided."<<endl;
40

cout<<endl;
41

}
42

else
43

{
44

cout<<"Collection #"<<cas<<":"<<endl;
45

cout<<"Can be divided."<<endl;
46

cout<<endl;
47

}
48

}
49

return 0;
50

}
51

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: pku3038 貪心加優先隊列 pku 2586 貪心 pku 1328 貪心 pku 1064 Cable master 二分搜索 pku 1915 廣搜 pku 1315 回溯法 pku 1651 矩陣連乘《計算機算法設計與分析》第二版王曉東 “最大m字段和優化函數”——P57注釋 pku 2109 一句話就能AC得題目？ pku 3620簡單搜索

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Onway

導航

隨筆分類(60)

文章分類(34)

收藏夾(15)

博友鏈接

搜索

最新評論

pku 1014 Dividing 多重背包