pku1010 STAMPS (搜索好题)

题目：

题目大意是说有多种类型的邮票，邮票有很多种面值(注意:不同类型的邮票有可能是同种面值)，现在给出顾客要求的总价值的邮票。如果不能给出，则输出none;如果能给出，要求求出顾客得到邮票的最佳方案。

最佳方案定义如下：

1，如果得到邮票的总价值符合顾客要求的价值，则其中邮票种类最多的方案为最佳方案；

2，承上，如果邮票种类相同，则邮票张数最少的为最佳方案；

3，承上，如果邮票的最少张数也相同，则各方案中拥有单张最大面值邮票的方案为最佳方案；

4，承上，如果各方案中单张最大面值邮票的面值也相等的话，则输出tie.

其中邮票的最大种类为25种(实际上大于25种，摘自discuss)，每位顾客可得到的邮票张数不超过4张。

 

分析，由于顾客可得到的邮票张数不超过4张，于是每一种邮票可取的可能性有5种，即取0张，1张，2张，3张，4张。。。这样就可以得出一种搜索策略，对每一种邮票可取的张数进行搜索。在搜索过程中记录下各种方案的邮票种类，最大面值，张数。这样搜出一种方案时，经过和已经搜索出的最佳方案进行比较。记录下最佳方案，并记下最佳方案有多少种，如果超过1种就输出tie。

my code:

 

/*

ax[i]:第i种邮票的面值

need:顾客所需的总价值

answer:最佳方案的种数

p:搜索到第p种方案

x[i]:记录下一种方案中第i种邮票的张数

ans[i]:最佳方案中第i种邮票的张数

sum[i]:搜索到第i种邮票时，所有邮票的总价值

have:标志有没有解，有的话为1,否则为0

kind[i]:搜索到第i种邮票时总的种类数

sumnum[i]:搜索到第i种邮票时总的邮票张数

tmax[i]:搜索到第i种邮票时，最大的面值

maxkind:临时最佳方案的邮票种类

maxvalue:临时最佳方案中邮票的最大面值

maxnum:临时最佳方案中邮票的张数

count:最佳方案中邮票的种类数

n:邮票的种类数

*/

#include<iostream>
using namespace std;
int ax[100],need,answer,p,x[100],ans[100];
int sum[100],have,kind[100],sumnum[100],tmax[100];
int maxkind,maxvalue,maxnum,count,n;
void res(int p)
{
    int i,j;
    for(i=0;i<=4;i++)//第p种邮票取的张数
   {
        if(i)kind[p]=kind[p-1]+1;
        else kind[p]=kind[p-1];
        sumnum[p]=sumnum[p-1]+i;
        sum[p]=sum[p-1]+i*ax[p];
        x[p]=i;
        if(i&&ax[p]>tmax[p-1]) tmax[p]=ax[p];else tmax[p]=tmax[p-1];
        if(sum[p]>need) break;
        if(sum[p]<need&&sumnum[p]<4&&p<n) res(p+1);
        if(!i)continue;
        if(sum[p]==need&&sumnum[p]<=4&&p<=n)
        {
            have=1;
            if(maxkind<kind[p])
            {
                answer=1;count=kind[p];
                for(j=1;j<=p;j++) ans[j]=x[j];ans[0]=p;
                maxvalue=tmax[p];
                maxnum=sumnum[p];
                maxkind=kind[p];
            }
            else if(maxkind==kind[p]&&sumnum[p]<maxnum)
            {
                answer=1;count=kind[p];
                for(j=1;j<=p;j++) ans[j]=x[j];ans[0]=p;
                maxvalue=tmax[p];
                maxnum=sumnum[p];
            }
            else if(maxkind==kind[p]&&maxnum==sumnum[p]&&maxvalue<tmax[p])
            {
                answer=1;count=kind[p];
                for(j=1;j<=p;j++) ans[j]=x[j];ans[0]=p;
                maxvalue=tmax[p];
            }
            else if(maxkind==kind[p]&&maxnum==sumnum[p]&&maxvalue==tmax[p])
                answer++;
        }
    }
}
int main()
{
    int i,j,k;i=1;
    while(cin>>ax[i++])
    {
        if(ax[i-1]==0)
        {
            n=i-1;
            while(cin>>need&&need!=0)
            {
                memset(ans,0,sizeof(ans));
                kind[0]=sumnum[0]=tmax[0]=0;
                maxkind=maxnum=maxvalue=0;
                answer=0;sum[0]=0;have=0;count=0;
                res(1);
                if(have==0) {cout<<need<<" ---- none"<<endl;continue;}
                else if(answer==1)
                {
                    cout<<need<<" ("<<count<<"): ";
                    for(i=1;i<=ans[0];i++)
                        for(j=1;j<=ans[i];j++)
                        {
                            cout<<ax[i];
                            if(i==ans[0]&&j==ans[i])cout<<endl;
                            else cout<<" ";
                        }
                }
                else if(answer>=2)
                    cout<<need<<" ("<<count<<"): tie"<<endl;
            }    
            i=1;
        }
    }
    return 0;
}