POJ-1010 Stamps

【题目描述】

题目大意是：邮票发行商会发行不同面值、不同种类的邮票给集邮爱好者，集邮爱好者有总目标面额，通过不同的邮票组合（总数在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] = stampindex;

        FindStampsCombination(solution, noOfStamp+1, 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<int> myset;

myset.insert(10);      // 插入

set<int>::iterator set_it = myset.find(11);

                        // 查找

myset.count(7);         // 计数

myset.erase(10);        // 删除

// 遍历

set<int>::iterator it; //定义前向迭代器

// 反向迭代器：set<int>::reverse_iterator

 for(it = myset.begin(); it != myset.end(); it++)

{

    //...

}

【附：完整源码】

#include <iostream>

#include <vector>

#include <set>

using namespace std;

typedef struct solutionattributes

{

    int No;

    int Types;

    int Number;

    int Max;

}SolutionAttributes;

int stamps[126];        // 存储邮票种类

int stampType;            // 邮票种类数

int customer;

vector<int*> 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<<customer<<" ---- none"<<endl;

    }

    else if (solutions.size() > 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"<<endl;

    }

    else

    {

        cout<< customer <<" ("<< sap[0].Types <<"):";

        int no = sap[0].No;

        int tempStamps[4] = {-1, -1, -1, -1};

        for (int i(0); i < 4; i++)

        {

            if (solutions.at(no)[i] != -1)

                tempStamps[i] = stamps[ solutions.at(no)[i] ];

        }

        qsort(tempStamps, 4, sizeof(tempStamps[0]), Compare);

        for (int i(0); i < 4; i++)

        {

            if (tempStamps[i] >= 0)

            {

                cout<<" "<<tempStamps[i];

            }

        }

        cout<<endl;

    }

}

int CountTypes(int s[4])

{

    set<int> 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;

    }

}

巴特西

POJ-1010 Stamps

最新文章

热门文章