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
第一种解法,套用前面几篇博文提到的背包问题揭发。程序如下:
// acm2.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>
using namespace std;
#define MAXNUM 6
#define MAXV 100000
int F[MAXV];
int max(int i,int j){
return i>j?i:j;
}
void zeroPack(int v,int weight,int value){
for(int i=v;i>=weight;i--){
F[i]=max(F[i],F[i-weight]+value);
}
}
void completePack(int v,int weight,int value){
for(int i=weight;i<=v;i++){
F[i]=max(F[i],F[i-weight]+value);
}
}
void multiplePack(int v,int weight,int value,int num){
if(weight*num>=v)
completePack(v,weight,value);
else{
int count=num,k=1;
while(k<count){
zeroPack(v,k*weight,k*value);
count-=k;
k=k+k;
}
zeroPack(v,count*weight,count*value);
}
}
int main(){
int n[10],i=0,totalNum=0,k=1;
while(true){
int bin=0;
for(i=1;i<=MAXNUM;i++){
cin>>n[i];
totalNum+=n[i]*i;
bin|=n[i];
}
if(!bin)
break;
F[0]=0;
for(i=1;i<MAXV;i++)
F[i]=0xffffffff;
if(totalNum&0x01){
cout<<"Collection #"<<k<<":\n"<<"Can't be divided."<<endl<<endl;
}else{
int num=totalNum>>1;
for(i=1;i<=MAXNUM;i++){
multiplePack(num,i,i,n[i]);
}
if(F[num]==num){
cout<<"Collection #"<<k<<":\n"<<"Can be divided."<<endl<<endl;
}
else
cout<<"Collection #"<<k<<":\n"<<"Can't be divided."<<endl<<endl;
}
k++;
}
}
第二种解法:DFS
// acm.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
#define NUMMAX 6
int n[NUMMAX];
bool flag=false;
void DFS(int value,int numMax,int weight){
if(value==weight){
flag=true;
return;
}
for(int i=numMax;i>=1;i--){
if(n[i]){
if(i+value<=weight){
n[i]--;
DFS(value+i,i,weight);
if(flag==true)
break;
}
}
}
}
int main(){
int numMax=0;
for(int i=1;i<=6;i++)
cin>>n[i];
for(int i=1;i<=6;i++)
numMax+=n[i]*i;
if(numMax%2!=0)
cout<<"no "<<endl;
else{
DFS(0,6,numMax/2);
if(flag==false)
cout<<"no"<<endl;
else
cout<<"yes"<<endl;
}
}
分享到:
相关推荐
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
背包 背包问题 背包算法 背包 noip 竞赛 信息技术 基础算法
算法效果较为良好,实现背包问题价值最大,采用遗传算法实现的比较不错的结果
贪心算法 背包问题 c语言 绝对无误 运行成功
回溯算法解0--1背包问题
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
背包问题.本算法比较清晰,易读。...背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
用禁忌搜索算法求解背包问题。假设背包容量一定,已知每种物品的体积和价值,求出使价值最大的最优解。
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
贪心算法解背包问题,供读者参考,我想看看有没有动态规划算法的解决办法
背包问题PSO(粒子群算法,Particle Swarm Optimization)基本算法代码,仅供参考
通过遗传算法实现背包问题最优解求解,包括代码文档。
背包问题之贪婪算法求解C语言源代码).背包问题之贪婪算法求解C语言源代码).
0-1背包问题(贪心算法)C语言源程序. 物品名称、物品效益、物品重量、物品的效益重量比等定义了物品的结构体。
01背包问题的贪心算法,详细解析,令你很快懂的01背包问题中的贪心算法思想
贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现...
背包问题:背包问题的贪心算法要求按照单位容量效益值的高低的量度标准进行排序,然后再分级选取, 求得最优解。实现此算法,物品个数,每件物品的效益值,容量值,背包容量值都由键盘输入; 输出结果要有每件物品的...
针对基本粒子群算法在背包问题上表现的不足,在基本粒子群算法的基础上运用模糊规则表加入了新 的扰动因子,提出了一种新的算法———模糊粒子群算法。该算法结合了模糊控制器中输入/输出的模糊化处理 和粒子群寻优...
算法,背包问题,贪心算法 讲述背包问题。对于学习这一部分的学习者,可以起作用。
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...