Dividing 03多重背包问题
DividingTime Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 8 Accepted Submission(s) : 2
Problem 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 describes one collection of marbles to be divided. The lines consist of six non-negative integers n1, n2, ..., 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 colletcion, 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.
用到n[i]=n[i]%10; mod10 跟以前的情况就会是一致的否则的话就会超时
[cpp]
<SPAN style="FONT-SIZE: 14px">#include<cstdio>
#include<cstring>
using namespace std;
int dp[60500];
int main()
{
int n[7];
int v[7];
int sum=0;
int test=1;
while(scanf("%d",&n[1])!=EOF)
{
memset(dp,0,sizeof(dp));
int sum=n[1];
int t;
for(int i=2; i<=6; i++)
{
scanf("%d",&t);
n[i]=t%10;
sum+=i*n[i];
}
if(n[1]==0&&n[2]==0&&n[3]==0&&n[4]==0&&n[5]==0&&n[6]==0) break;
if(sum%2==1)
{
printf("Collection #%d:\nCan't be divided.\n\n",test);
test++;
continue;
}
for(int i=1; i<=6; i++)
v[i]=i;
int V=sum/2;
dp[0]=1;
for(int i=1; i<=6; i++)
{
for(int j=0; j<n[i]; j++)
{
for(int k=V; k>=v[i]; k--)
{
if(dp[k-v[i]])
dp[k]=1;
}
}
}
// for(int i=V;i>=0;i--)
//printf("%d %d\n",dp[i],i);
if(dp[V]==1)
{
printf("Collection #%d:\nCan be divided.\n\n",test);
test++;
}
else
{
printf("Collection #%d:\nCan't be divided.\n\n",test);
test++;
}
}
return 0;
}
</SPAN>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[60500];
int main()
{
int n[7];
int v[7];
int sum=0;
int test=1;
while(scanf("%d",&n[1])!=EOF)
{
memset(dp,0,sizeof(dp));
int sum=n[1];
int t;
for(int i=2; i<=6; i++)
{
scanf("%d",&t);
n[i]=t%10;
sum+=i*n[i];
}
if(n[1]==0&&n[2]==0&&n[3]==0&&n[4]==0&&n[5]==0&&n[6]==0) break;
if(sum%2==1)
{
printf("Collection #%d:\nCan't be divided.\n\n",test);
test++;
continue;
}
for(int i=1; i<=6; i++)
 
补充:软件开发 , C++ ,
上一个:如何实现给一个结构体队列分配内存空间
下一个:线程间的同步概述
- 更多C/C++疑问解答:
- 关于c++的cout输出的问题。
- 在学校里学过C和C++,不过学的很一般,现在自学C#,会不会很难?
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
- c++数据结构内部排序问题,整数排序
- 2012九月计算机二级C语言全国题库,,急求急求
- 如果assert只有一个字符串作为参数,是什么意思呢?
- C语言中,哪些运算符具有左结合性,哪些具有右结合性,帮忙总结下,谢谢了!
- 为什么用结构体编写的程序输入是,0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型,用C或C++都行,多谢各位大侠啊,非常感谢!
- 为什么这个程序求不出公式?
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊