hdu--1059--多重背包||DP||搜索

碎碎念-----

　　突然觉得好无聊~~ 还好只有4天了~~

　　直接上题吧~~

　　　　touch me

　　使用多重背包的代码是转自---键盘上的舞者---- 写得特别有想法

　　使用dp的代码是porker写的..

　　使用搜索的我一开始是将价值从低到高搜索的这样TLE了,,因为速度实在是太慢了假如有arr[k]个那么我要有arr[k]+1个操作...

　　但是按价值从高到低的搜索只要遵循尽量在不到sum/2的时候去搜就是了有就添加进来...但这个方法的正确性没有得到证明...

 1 #include <iostream>
 2 using namespace std;
 3 int arr[7];
 4 int sum, cnt = 1;
 5 
 6 bool dp[7][120001];
 7 
 8 int main()
 9 {
10     cin.sync_with_stdio(false);
11     while (cin >> arr[1])
12     {
13         sum = 0;
14         sum += arr[1];
15         for (int i = 2; i <= 6; i++)
16         {
17             cin >> arr[i];
18             sum += arr[i] * i;
19         }
20         if (!sum)
21             break;
22         cout << "Collection #" << cnt++ << ":" << endl;
23         if (sum & 1) {
24             cout << "Can't be divided." << endl << endl;
25             continue;
26         }
27         memset(dp, false, sizeof(dp));
28         dp[0][0] = true;
29         for (int i = 1; i <= 6; i++) {
30             for (int j = sum; j >= 0; j--) {
31                 if (dp[i - 1][j] == false) continue;
32                 for (int k = 0; k <= arr[i]; k++) {
33                     if (j + k*i >= sum) break;
34                     if (dp[i][j + k*i]) break;
35                     dp[i][j + k*i] = true;
36                 }
37             }
38         }
39         if (dp[6][sum / 2]) {
40             cout << "Can be divided." << endl;
41         }
42         else {
43             cout << "Can't be divided." << endl;
44         }
45         cout << endl;
46     }
47     return 0;
48 }

View Code

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 int dp[100000];
 7 
 8 int main()
 9 {
10     int a[11],sum,v,i,j,k,cnt,cas = 1;
11     while(~scanf("%d",&a[1]))
12     {
13         sum = a[1];
14         for(i = 2;i<=6;i++)
15         {
16             scanf("%d",&a[i]);
17             sum+=i*a[i];
18         }
19         if(!sum)
20         break;
21         printf("Collection #%d:
",cas++);
22         if(sum%2)//总和为奇数，必定不能平分
23         {
24             printf("Can't be divided.

");
25             continue;
26         }
27         v = sum/2;
28         memset(dp,0,sizeof(dp));
29         dp[0] = 1;
30         for(i = 1;i<=6;i++)
31         {
32             if(!a[i])
33             continue;
34             for(j = 1;j<=a[i];j*=2)//二进制优化
35             {
36                 cnt = j*i;
37                 for(k = v;k>=cnt;k--)
38                 {
39                     if(dp[k-cnt])//必须前面的能够放入背包，现在的才能放入背包
40                     dp[k] = 1;
41                 }
42                 a[i]-=j;
43             }
44             cnt = a[i]*i;//剩下的
45             if(cnt)
46             {
47                 for(k = v;k>=cnt;k--)
48                 {
49                     if(dp[k-cnt])
50                     dp[k] = 1;
51                 }
52             }
53         }
54         if(dp[v])
55         printf("Can be divided.

");
56         else
57         printf("Can't be divided.

");
58     }
59 
60     return 0;
61 }

View Code

 1 #include <iostream>
 2 using namespace std;
 3 int arr[7];
 4 int sum , cnt = 1;
 5 bool flag;
 6 
 7 void dfs( int pos , int cnt )
 8 {
 9     if( cnt*2 == sum )
10     {
11         flag = true;
12         return;
13     }
14     if( flag || cnt*2>sum )
15     {
16         return;
17     }                
18     for( int i = pos ; i>=1 ; i-- )
19     {
20         if( arr[i] )
21         {
22             if( cnt+i<=sum/2 )
23             {
24                 arr[i]--;
25                 dfs( i , cnt+i );
26                 if( flag )
27                     break;
28             }
29         }    
30     }
31 }
32 
33 int main()
34 {
35     cin.sync_with_stdio(false);
36     while( cin >> arr[1] )
37     {
38         flag =false;
39         sum = 0;
40         sum += arr[1];
41         for( int i = 2 ; i<=6 ; i++ )
42         {
43             cin >> arr[i];
44             sum += arr[i]*i;
45         }
46         if( !sum )
47             break;
48         cout << "Collection #"<< cnt++ <<":"<<endl;
49         if( sum&1 )
50         {
51             cout << "Can't be divided." << endl << endl;
52             continue;
53         }
54         dfs( 6 , 0 );
55         if( flag )
56             cout << "Can be divided." << endl << endl;
57         else
58             cout << "Can't be divided." << endl << endl;
59     }
60     return 0;
61 }

View Code

today:

　　你看别人说他千般不好他说过一句没有。

　　悲伤的人总是在笑。

just follow your heart