poj-1014 Dividing

水深无声 2022-05-31 00:58 174阅读 0赞

Dividing

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;73587</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;19211</td> 
  </tr> 
 </tbody> 
</table>

Description

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.

Input

Each line in the input file describes one collection of marbles to be divided. The lines contain six non-negative integers n1 , . . . , n6 , where ni is the number of marbles of value i. So, the example from above would be described by the input-line "1 0 1 2 0 0". The maximum total number of marbles will be 20000.   
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.

Output

For each collection, output "Collection \#k:", where k is the number of the test case, and then either "Can be divided." or "Can't be divided.".   
Output a blank line after each test case.

Sample Input

1 0 1 2 0 0 
    1 0 0 0 1 1 
    0 0 0 0 0 0

Sample Output

Collection #1:
    Can't be divided.
    
    Collection #2:
    Can be divided.

Source

[Mid-Central European Regional Contest 1999][]

这道题可以用多重背包的方法来解，但是我还不怎么会多重背包，看了大佬的题解用了递归的方法来解的：

思路：开始先对物品进行一次判断，判断是否满足能平分，然后搜索，感觉和NYOJ求部份和那道题类似。

代码：

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int s[11],flag;
    int dfs(int half,int sum,int num)
    {
        int i;
        if(sum==half)//条件满足
        {
            flag=1;
            return flag;
        }
        else
        {
            for(i=num;i>=1;i--)//从最大的那个开始找
            {
                if(s[i])//如果这件物品还有剩余
                {
                    if(sum+i<=half)//小于等于一半才能继续
                    {
                        s[i]--;//这件物品的数量减一
                        dfs(half,sum+i,i);//对当下物品进行搜索
                        if(flag)
                            break;
                    }
                }
            }
        }
        return flag;
    }
    int main()
    {
        int a,b,c,d,e,f,q=1,sum,half;
        while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f)!=EOF)
        {
            if(a==0&&b==0&&c==0&&e==0&&f==0)
                break;
            s[1]=a;
            s[2]=b;
            s[3]=c;
            s[4]=d;
            s[5]=e;
            s[6]=f;
            sum=0;
            for(int i=1; i<=6; i++)
                sum+=i*s[i];
            printf("Collection #%d:\n",q++);
            if(sum%2)//如果不是偶数，肯定不能均分
            {
                printf("Can't be divided.\n\n");
                continue;
            }
            else
                half=sum/2;
            flag=0;//进行搜索
            if(dfs(half,0,6))
            {
                 printf("Can be divided.\n\n");
                 continue;
            }
            else
            {
                printf("Can't be divided.\n\n");
                continue;
            }
        }
        return 0;
    }

[Mid-Central European Regional Contest 1999]: http://poj.org/searchproblem?field=source&key=Mid-Central+European+Regional+Contest+1999