POJ1010 Stamps

题目来源：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[4];
    int types;
    int count;
    int maxValue;
};

int types[100];
int typeCount;
int customer;
int customerCount;
vector<Solution> sVector;
bool isTie;

int getTypes(int i0, int i1, int i2 = -1, int i3 = -1) {
    if (i3 == -1 && i2 == -1) {
        if (i0 == i1) {
            return 1;
        } else {
            return 2;
        }
    } else if (i3 == -1) {
        if (i0 == i1 && i1 == i2) {
            return 1;
        } else if (i1 == i2 || i0 == i1 || i0 == i2) {
            return 2;
        } else {
            return 3;
        }
    } else if(i0 == i1 && i1 == i2 && i2 == i3) {
        return 1;
    } else if (i0 != i1 && i0 != i2 && i0 != i3 && i1 != i2 && i1 != i3 && i2 != i3) {
        return 4;    
    } 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 3;
    } else {
        return 2;
    }
}

int findBestSolution() {
    int bestSolution = 0;
    if (sVector.size() == 1) return 0;
    for (int i = 1; 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 = 0; i < sulotion.count; i++) {
        cout << " " << sulotion.stamps[i]; 
    }
    cout << endl;
}
int main(void) {
    while(cin >> types[0]) {
        while (types[typeCount] != 0) {
            cin >> types[++typeCount];
        }
        while (cin >> customer) {
            if (customer == 0) {
                break;
            }
            if (types[0] * 1 > customer) {
                cout << customer << " ---- none" << endl;
                continue;
            }
            if (types[typeCount - 1] * 4 < customer) {
                cout << customer << " ---- none" << endl;
                continue;
            }
            for (int i0 = 0; i0 < typeCount; i0++) {
                if(types[i0] == customer) {
                    Solution solution;
                    solution.stamps[0] = types[i0];
                    solution.stamps[1] = 0;
                    solution.stamps[2] = 0;
                    solution.stamps[3] = 0;
                    solution.maxValue = types[i0];
                    solution.count = 1;
                    solution.types = 1;
                    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[0] = types[i0];
                            solution.stamps[1] = types[i1];
                            solution.stamps[2] = 0;
                            solution.stamps[3] = 0;
                            solution.maxValue = types[i1];
                            solution.count = 2;
                            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[0] = types[i0];
                                    solution.stamps[1] = types[i1];
                                    solution.stamps[2] = types[i2];
                                    solution.stamps[3] = 0;
                                    solution.maxValue = types[i2];
                                    solution.count = 3;
                                    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[0] = types[i0];
                                            solution.stamps[1] = types[i1];
                                            solution.stamps[2] = types[i2];
                                            solution.stamps[3] = types[i3];
                                            solution.maxValue = types[i3];
                                            solution.count = 4;
                                            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() == 0) {
                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 = 0;
        typeCount = 0;
        sVector.clear();    
    }
    system("pause");
    return 0;
}