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;
}
UVA 100: The 3n + 1 problem
题目大意：
3n+1问题是一个非常经典的数学问题，目前还没有人能够证明。一个数通过3N+1的算法会等到一个序列，序列肯定会以1结尾，例如22的序列是22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1，它的序列长度是16.
现在要给你一个范围,n,m，让你求出这个范围你每个数的3N+1序列最长是多少。
解题思路：
这个问题是UVA中最简单的题目，打算按那个UVA的难度排行表一题一题做下去。
解决办法是将这个范围内的数，每个都求出它的序列长度，然后保留最大的长度。
这题有一个trick,就是给你n,m并不是一定是n<=m，因为这个做错一次，所以做题时候要细心注意细节条件。一些没有提到的条件要想到。
解题代码：
#include<iostream>
using namespace std;
int t3n1(int n){
int num=1;
while(n!=1){
if(n%2)
n=3*n+1;
else
n=n/2;
num++;
}
return num;
}
int work(int n,int m){
int max=0,tmp;
for(int i=n;i<=m;i++)
if(max<(tmp=t3n1(i)))
max=tmp;
}
return max;
}
int main(){
int n,m;
while(cin>>n>>m){
if(n>m){
cout<<n<<' '<<m<<' '<<work(m,n)<<endl;
}
else
cout<<n<<' '<<m<<' '<<work(n,m)<<endl;
}
return 0;
}
扩展知识：http://www.equn.com/3x+1/