加载中...

POJ 1010 - STAMPS


问题描述

题意比较难懂。大致如下:

第一行数字是邮票的面值,每一个数字就是一个不同的种类,哪怕面值相同。以 0 结束。

第二行数字是顾客所需要的邮票总面值。每个数字就是一个顾客的需求,以 0 结束。

每两行是一组 case。以 EOF 结束输入。

顾客是集邮爱好者,所以你必须尽可能的给他不同种类的邮票。

但是一位顾客最多只能拿 4 张邮票。

显然,我们拥有的邮票就是第一行中的数据。

解题思路

DFS 寻找所有的解,再逐一比较寻找最优解,剪枝是关键。

关于 tie :

  • 满足顾客需求的解就是可行解
  • 邮票种类最多的可行解为最优
  • 如果存在两个以上的最优解的邮票种类是一样的,张数最少的更优
  • 张数也一样的话,这些最优解中最大面值较大的更优。
  • 若邮票种类、张数、最大面值三者都分别相同,则认为这些最优解相同,输出 tie

没有解就是 none

解法大致有三种

  1. 枚举。反正最多拿 4 张,可以 4 重循环暴搜最优解。
  2. DFS。每次搜索后,如果有解,更新最优解,关键在剪枝。
  3. 三维DP。这个没怎么研究,不太懂……

我用的是第二种 DFS

关于剪枝

  1. 最多拿四张邮票,如果同一面值的邮票种类超过 5,以 5 计算。 为什么不以 4 计算呢?因为 tie
  2. 若 DFS 的深度超过了 4,那么就返回。(最多四张邮票)
  3. 技巧剪枝: 先对输入的邮票按面值升序排序,DFS 到面值 k 时,不再搜索面值 <k 的邮票。 同时排序也是为了保证 DFS 的最优解的邮票种类最多。

测试数据

AC 源码

//Memory Time 
// 228K   0MS 

#include<iostream>
#include<algorithm>
using namespace std;

const int size=26;

int value[size];  //第i种邮票面值value[i]
int pv;  //value[]指针
int time[size];  //标记第i种邮票被分配过的次数

bool flag;  //标记是否已经出现过解
bool flag_tie;  //标记是否为tie
int solve[6];  //solve[0]:邮票张数  solve[5]:邮票种数  solve[1..4]:持有的邮票面值,0表示不持有
int BestSolve[6];  //最优解

void dfs(int need,int num,int type,int pre);  //need:总面值 num:邮票张数  type:邮票种数
int max4(int* s);  //返回s[1..4] 4个数中的最大值
void best(int num,int type);  //更新最优解

int main(void)
{
    while(true)
    {
        pv=0;
        int type[size]={0};  //面值为i的邮票的种数type[i]

        int tmp;
        while(true)
        {
            if(scanf("%d",&tmp)==EOF)
                exit(0);
            if(tmp==0)
                break;

            if(type[ tmp ]<5)     //剪枝,同面额的邮票种类超过5,则按5计算
            {
                type[ tmp ]++;
                value[pv++]=tmp;
            }
        }
        sort(value,value+pv);  //要使分配的邮票的种类尽可能多
                               //只需在搜索前把邮票面值升序排序,从最小面额开始搜索

        int need;  //顾客需求
        while(cin>>need && need)
        {
            flag=false;
            flag_tie=false;
            memset(solve,0,sizeof(solve));
            memset(BestSolve,0,sizeof(BestSolve));
            memset(time,0,sizeof(time));

            /*Search*/

            dfs(need,0,0,0);

            /*Output*/

            cout<<need;
            if(BestSolve[0]==0)
                cout<<" ---- none"<<endl;
            else
            {
                cout<<" ("<<BestSolve[5]<<"):";

                if(flag_tie)
                    cout<<" tie"<<endl;
                else
                {
                    sort(BestSolve+1,BestSolve+5);
                    for(int i=1;i<=4;i++)
                    {
                        if(BestSolve[i]==0)
                            continue;
                        cout<<' '<<BestSolve[i];
                    }
                    cout<<endl;
                }
            }
        }
    }
    return 0;
}

void dfs(int need,int num,int type,int pre)  //need:总面值 num:邮票张数  type:邮票种数
{
    if(num==5)  //剪枝,顾客持有邮票张数不超过4
        return;

    if(need==0)
    {
        if(!flag)
        {
            if(type==BestSolve[5])  //最优解的种类type相同
            {
                if(num==BestSolve[0])  //最优解的张数num相同
                {
                    int Maxs=max4(solve);  //solve的最大面值
                    int MaxBs=max4(BestSolve); //BestSolve的最大面值

                    if(Maxs==MaxBs)    //存在多个最优解
                        flag_tie=true;
                    else if(Maxs>MaxBs)  //种类、张数都相同的情况下,最大面值较大的解优先
                    {
                        flag_tie=false;
                        best(num,type);
                    }
                }
                else if(num<BestSolve[0])  //种类相同情况下,张数少的解优先
                {
                    flag_tie=false;
                    best(num,type);
                }
            }
            else if(type>BestSolve[5])  //种类多的解优先
            {
                flag_tie=false;
                best(num,type);
            }
        }
        else
        {
            flag=true;
            best(num,type);
        }

        return;
    }

    for(int i=pre;i<pv;i++)   //i=pre 剪枝,不重复搜索比当前面值小的邮票,同时避免错误的tie
    {
        if(need>=value[i])
        {
            solve[num+1]=value[i];

            if(time[i]!=0)
            {
                time[i]++;
                dfs(need-value[i],num+1,type,i);
            }
            else
            {
                time[i]++;
                dfs(need-value[i],num+1,type+1,i);
            }

            solve[num+1]=0;  //回溯
            time[i]--;
        }
        else
            return;  //value已排序
    }

    return;
}

int max4(int* s)  //返回s[1..4] 4个数中的最大值
{
    int a=s[1]>s[2]?s[1]:s[2];
    int b=s[3]>s[4]?s[3]:s[4];

    return a>b?a:b;
}

void best(int num,int type)  //更新最优解
{
    BestSolve[0]=num;
    BestSolve[5]=type;

    for(int k=1;k<=4;k++)
        BestSolve[k]=solve[k];
    return;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录