【题目描述】

题目大意是：邮票发行商会发行不同面值、不同种类的邮票给集邮爱好者，集邮爱好者有总目标面额，通过不同的邮票组合（总数在4张以内）达到该面值，卖给集邮爱好者。另外，发行商发行的邮票面值最多25种，但有可能同种面值有好几种邮票，甚至超过25种。

最佳方案满足以下要求：

• 邮票种类数最多；
• 如果种类数相同，则张数少者，更优；
•  如果张数也相同，则单张面值最大者；
• 如果以上都相同，则无最佳方案（平局tie）；

 

【思路分析】

1. 邮票种类存储策略

由于最多只有四张邮票给集邮爱好者，我们可以设定同一面值的邮票最多存储5种，因为再多的种类组成的总价值也是一样的，输出的格式也一样。

这里取5种是因为要判断是否有tie的情况，设想某种邮票有N种(N>4)，且这N种中任取4种为最优解时，此时应该输出”tie”，而如果只取4种，是不会输出”tie”。

所以，25种面值*最多存储的5种=125，为邮票的存储空间。HasMaxSameStamp函数判断该面值邮票是否已经达到5种。

int stamps[126];        // 存储邮票种类int stampType;          // 邮票种类数bool HasMaxSameStamp(int newstamp){    int hasSameNum = 0;    for (int i(0); i < stampType; i++)    {        if (stamps[i] == newstamp)        {            hasSameNum += 1;            if (hasSameNum >= 5)                return true;        }    }    return false;}

 

2. 深度优先法搜索所有解

解为最多四张邮票，用int solution[4]暂时存储进行搜索，noOfStamp为当前考虑的solution[noOfStamp]中的邮票，lastIndex为了避免重复搜索，将不搜索已搜索过的邮票定为策略，其意义为接下来的解只从数组编号为lastIndex的邮票开始搜索。

void FindStampsCombination(int solution[4], int noOfStamp, int lastIndex){    if (IsASolution(solution))    {        int *p = new int[4];        memcpy(p, solution, sizeof(int)*4);        solutions.push_back(p);        return ;    }     if (noOfStamp >= 4)        // 邮票数已经为4张，应该被剪枝，回溯        return ;            for (int stampindex( lastIndex ); stampindex < stampType; stampindex++)    {                        solution[noOfStamp] = -1;      }}

 

3. 找出最优解

将所有解存入vector<int*> solutions中，以题目要求的比较策略进行排序比较。先比较类型数，更多的取胜；再比较数量，少的取胜；最后比较单张面值最大的。

typedef struct solutionattributes{    int No;    int Types;    int Number;    int Max;}SolutionAttributes;int CompareSolution(const void* a, const void* b){    SolutionAttributes *pa = (SolutionAttributes*)a;    SolutionAttributes *pb = (SolutionAttributes*)b;    if ((*pa).Types != (*pb).Types)    {        return (*pb).Types - (*pa).Types;    }     else if ((*pa).Number != (*pb).Number)    {        return (*pa).Number - (*pb).Number;    }    else    {        return (*pb).Max - (*pa).Max;            }}

 

【小结】

本题关注的要点在于：DFS搜索（及剪枝、回溯），比较函数的编写规则，以及集合set的用法。

1. 回溯法的程序编写见本题的“2.深度优先法搜索所有解”；

2. 比较函数规则：参数a, b，如果返回大于0，则a到b的后面去，记住这一原则即可；

3. 集合set的用法：

set
     
       myset;myset.insert(10);      // 插入set
      
       ::iterator set_it = myset.find(11);                        // 查找myset.count(7);         // 计数myset.erase(10);        // 删除// 遍历set
       
        ::iterator it; //定义前向迭代器  // 反向迭代器：set
        
         ::reverse_iterator for(it = myset.begin(); it != myset.end(); it++) {    //...}
        
       
      
     

 

【附：完整源码】

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef struct solutionattributes{    int No;    int Types;    int Number;    int Max;}SolutionAttributes;int stamps[126];        // 存储邮票种类int stampType;            // 邮票种类数int customer;vector
        
          solutions;void InitialForStamps();bool HasMaxSameStamp(int newstamp);void FindStampsCombination(int solution[4], int noOfStamp, int lastIndex);bool IsASolution(int s[4]);int Compare(const void* a, const void* b);void OutputBestSolution();int CountTypes(int s[4]);int CountNumber(int s[4]);int CountMax(int s[4]);int CompareSolution(const void* a, const void* b);int main(){    int stampValue;    while (scanf("%d", &stampValue) != EOF)    {        // 读取邮票种类        InitialForStamps();        while (true)        {            if (stampValue == 0)                break;            if ( !HasMaxSameStamp(stampValue) )            {                stamps[ stampType++ ] = stampValue;            }            cin>>stampValue;        }        // 读取顾客需求，并处理，输出        while (true)        {            cin>>customer;            if (customer == 0)                break;            solutions.clear();            int solution[4] = {-1,-1,-1,-1};        // 四张邮票            FindStampsCombination(solution, 0, 0);            OutputBestSolution();        }    }    return 0;}void InitialForStamps(){    memset(stamps, 0, sizeof(stamps));    stampType = 0;}bool HasMaxSameStamp(int newstamp){    int hasSameNum = 0;    for (int i(0); i < stampType; i++)    {        if (stamps[i] == newstamp)        {            hasSameNum += 1;            if (hasSameNum >= 5)                return true;        }    }    return false;}void FindStampsCombination(int solution[4], int noOfStamp, int lastIndex){    if (IsASolution(solution))    {        int *p = new int[4];        memcpy(p, solution, sizeof(int)*4);        solutions.push_back(p);        return ;    }     if (noOfStamp >= 4)        // 邮票数已经为4张，应该被剪枝，回溯        return ;            for (int stampindex( lastIndex ); stampindex < stampType; stampindex++)    {        solution[noOfStamp] = stampindex;        FindStampsCombination(solution, noOfStamp+1, stampindex);        solution[noOfStamp] = -1;    }}bool IsASolution(int s[4]){    int stampsTotalValue = 0;    for (int i(0); i < 4; i++)    {        stampsTotalValue += (s[i] < 0? 0 : stamps[ s[i] ]);    }    return (stampsTotalValue == customer);}int Compare(const void* a, const void* b){    int *pa = (int*)a;    int *pb = (int*)b;    return (*pa) - (*pb);}void OutputBestSolution(){    SolutionAttributes *sap = new SolutionAttributes[solutions.size()];    for (int i(0); i < solutions.size(); i++)    {        sap[i].No = i;        sap[i].Types = CountTypes(solutions.at(i));        sap[i].Number = CountNumber(solutions.at(i));        sap[i].Max = CountMax(solutions.at(i));    }    qsort(sap, solutions.size(), sizeof(sap[0]), CompareSolution);        if (solutions.size() == 0)    {        cout<
         
          <<" ---- none"<
          
            1 && sap[0].Types == sap[1].Types && sap[0].Number == sap[1].Number && sap[0].Max == sap[1].Max) { cout<< customer <<" ("<< sap[0].Types <<"): "<<"tie"<
           
            = 0) { cout<<" "<
            

types; for (int i(0); i < 4; i++) { if (s[i] >= 0) types.insert(s[i]); } return types.size();}int CountNumber(int s[4]){ int empty = 0; for (int i(0); i < 4; i++) { empty += (s[i] < 0); } return 4 - empty;}int CountMax(int s[4]){ int max = 0; for (int i(0); i < 4; i++) { if (s[i] >= 0) { max = max > stamps[ s[i] ]? max : stamps[ s[i] ]; } } return max;}int CompareSolution(const void* a, const void* b){ SolutionAttributes *pa = (SolutionAttributes*)a; SolutionAttributes *pb = (SolutionAttributes*)b; if ((*pa).Types != (*pb).Types) { return (*pb).Types - (*pa).Types; } else if ((*pa).Number != (*pb).Number) { return (*pa).Number - (*pb).Number; } else { return (*pb).Max - (*pa).Max; }}