UVA 102: Ecological Bin Packing

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38

题目大意：

     装箱问题也是背包问题是一个非常容易理解题意但是非常难的问题，是NP问题。但是本题是一个简单的垃圾分类问题。每个垃圾桶里面都有3个分别是棕色、绿色、白色的分类箱子，每个垃圾桶里面的每个箱子里面都有垃圾，现在要使每个垃圾桶里面只有一个颜色的箱子有垃圾，其它箱子里面的垃圾要移动到别个垃圾桶里面，要使移动的垃圾最少。

解题思路：

      枚举法，每个垃圾桶可以装的颜色都遍历一遍，求出移动最小的那个值就是答案，还要比较方案字符串，最小值相同输出字符串字典序小的。

解题代码：

#include<iostream>
#include<string>
using namespace std;
int a[9];
string s("BGC");
void work(){
	string s1=("BGC");
	int min=1<<31-1;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int z=0;z<3;z++)
				if(i!=j&&j!=z&&i!=z){
					string s2;
					s2+=s[i];
					s2+=s[j];
					s2+=s[z];
					int tmp=0;
				    for(int k=0;k<9;k++)
						if(i!=k&&k!=3+j&&k!=6+z)
							tmp+=a[k];
					if(min>tmp) min=tmp,s1=s2;
					else
						if(min==tmp){
							if(s1>s2) s1=s2;
						}
				}
	cout<<s1<<' '<<min<<endl;
}
int main(){
	while(cin>>a[0]){
		for(int i=1;i<9;i++)
				cin>>a[i];
		work();
	}
	return 0;
}

扩展知识：http://baike.baidu.com/view/841810.htm

• 全局相关文章
• 相关文章