题目来源：http://poj.org/problem?id=1010
题目大意：
某邮局要设计新的邮资管理软件，依据顾客的需要和现有的面值给顾客分派邮票。
该邮局有很多顾客是集邮爱好者。这些人希望得到最多种类不同的邮票。该邮局会发行同一面值的不同邮票。邮票的面值最大为25.
为节约成本，邮局希望尽可能少的重复邮票。（他们希望发行尽可能多的不同种类的邮票）。而且，邮局对一个客户一次最多卖4张邮票。
输入：程序的输入是多组两行的数据。以EOF结束。第一行是现有的邮票的面值，以0结束。第二行是一系列的客户需求。
输出：对于每一个客户，输出“最好”的邮票组合（邮票种类数最多）。面值和恰好为客户的需要，邮票张数最大为4。如果找不到这样的组合，输出“none”。如果有多个“最好”组合，选择邮票总数最少的一组，如果仍然相等，邮票面值中单张价格最高的最优，若仍然相等，输出“tie”。具体格式见Example Output.
Sample Input
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Sample Output
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
因为一次最多四张邮票，于是用了最傻的方法，找出所有可行的组合再按规则找最优解。另外测试数据中邮票面值实际是按升序输入的，若不按升序输入，则预先在程序中进行排序即可。拙劣代码奉上。
//////////////////////////////////////////////////////////////////////////
// POJ1010 Stamps
// Memory: 5356K Time: 32MS
// Language: C++ Result: Accepted
////////////////////////////////////////////////////////////////////////// #include <iostream>
#include <vector> using namespace std; class Solution {
public:
int stamps[];
int types;
int count;
int maxValue;
}; int types[];
int typeCount;
int customer;
int customerCount;
vector<Solution> sVector;
bool isTie; int getTypes(int i0, int i1, int i2 = -, int i3 = -) {
if (i3 == - && i2 == -) {
if (i0 == i1) {
return ;
} else {
return ;
}
} else if (i3 == -) {
if (i0 == i1 && i1 == i2) {
return ;
} else if (i1 == i2 || i0 == i1 || i0 == i2) {
return ;
} else {
return ;
}
} else if(i0 == i1 && i1 == i2 && i2 == i3) {
return ;
} else if (i0 != i1 && i0 != i2 && i0 != i3 && i1 != i2 && i1 != i3 && i2 != i3) {
return ;
} else if (i0 == i1 && i1 != i2 && i2 != i3 && i3 != i1
|| i0 == i2 && i0 != i1 && i0 != i3 && i1 != i3
|| i0 == i3 && i0 != i1 && i0 != i2 && i1 != i2
|| i1 == i2 && i0 != i1 && i2 != i3 && i0 != i3
|| i1 == i3 && i0 != i1 && i1 != i2 && i0 != i2
|| i2 == i3 && i2 != i0 && i2 != i1 && i0 != i1 ) {
return ;
} else {
return ;
}
} int findBestSolution() {
int bestSolution = ;
if (sVector.size() == ) return ;
for (int i = ; i < sVector.size(); i++) {
if (sVector[i].types > sVector[bestSolution].types) {
isTie = false;
bestSolution = i;
} else if (sVector[i].types == sVector[bestSolution].types) {
if (sVector[i].count < sVector[bestSolution].count) {
isTie = false;
bestSolution = i;
} else if (sVector[i].count == sVector[bestSolution].count) {
if (sVector[i].maxValue > sVector[bestSolution].maxValue) {
isTie = false;
bestSolution = i;
} else if (sVector[i].maxValue == sVector[bestSolution].maxValue) {
isTie = true;
}
}
}
}
return bestSolution;
} void Output(int sindex) {
Solution sulotion = sVector[sindex];
cout << " (" << sulotion.types << "):";
for(int i = ; i < sulotion.count; i++) {
cout << " " << sulotion.stamps[i];
}
cout << endl;
}
int main(void) {
while(cin >> types[]) {
while (types[typeCount] != ) {
cin >> types[++typeCount];
}
while (cin >> customer) {
if (customer == ) {
break;
}
if (types[] * > customer) {
cout << customer << " ---- none" << endl;
continue;
}
if (types[typeCount - ] * < customer) {
cout << customer << " ---- none" << endl;
continue;
}
for (int i0 = ; i0 < typeCount; i0++) {
if(types[i0] == customer) {
Solution solution;
solution.stamps[] = types[i0];
solution.stamps[] = ;
solution.stamps[] = ;
solution.stamps[] = ;
solution.maxValue = types[i0];
solution.count = ;
solution.types = ;
sVector.push_back(solution);
continue;
} else if (types[i0] < customer){
for (int i1 = i0; i1 < typeCount; i1++) {
if(types[i0] + types[i1] == customer) {
Solution solution;
solution.stamps[] = types[i0];
solution.stamps[] = types[i1];
solution.stamps[] = ;
solution.stamps[] = ;
solution.maxValue = types[i1];
solution.count = ;
solution.types = getTypes(i0, i1);
sVector.push_back(solution);
continue;
} else if (types[i0] + types[i1] < customer) {
for(int i2 = i1; i2 < typeCount; i2++) {
int sum = types[i0] + types[i1] + types[i2];
if(sum == customer) {
Solution solution;
solution.stamps[] = types[i0];
solution.stamps[] = types[i1];
solution.stamps[] = types[i2];
solution.stamps[] = ;
solution.maxValue = types[i2];
solution.count = ;
solution.types = getTypes(i0, i1, i2);
sVector.push_back(solution);
} else if (sum < customer){
for(int i3 = i2; i3 < typeCount; i3++) {
int sum = types[i0] + types[i1] + types[i2] + types[i3];
if(sum == customer) {
Solution solution;
solution.stamps[] = types[i0];
solution.stamps[] = types[i1];
solution.stamps[] = types[i2];
solution.stamps[] = types[i3];
solution.maxValue = types[i3];
solution.count = ;
solution.types = getTypes(i0, i1, i2, i3);
sVector.push_back(solution);
} else if (sum > customer) {
break;
}
}
} else {
break;
}
}
} else {
break;
}
}
} else {
break;
}
}
if (sVector.size() == ) {
cout << customer << " ---- none" << endl;
continue;
}
int bestSolution = findBestSolution();
if (isTie) {
cout << customer << " (" << sVector[bestSolution].types << "): tie" << endl;
} else {
cout << customer;
Output(bestSolution);
}
sVector.clear();
isTie = false;
}
customerCount = ;
typeCount = ;
sVector.clear();
}
system("pause");
return ;
}