题目大意（转这里）

给你一些邮票的面值，然后给你一些顾客给出的价钱，求出邮票的组合来满足每一位顾客，要求是最多四张邮票，每张可以用多次（其实最多也就四次，因为要求最多四张，否则就是none）。

如：邮票面值1 2 3 0；0代表这行结束

顾客的需求：7 4 0

结果：

7 (3): 1 1 2 3

4 (2): 1 3

解释一下：

由于每次有多种组合，那么如何取结果呢？

如果这些组合都能满足用户的的需求，那么

1.选种类最多的

2.如果种类相同，选总数最少的

3.如果总数相同，选邮票值组合最大值最大的那一组

4.如果连最大值也相同，那么就是tie

5。如果没有这样的组合，也就是不能用4张以内的邮票满足顾客，那么就是none

输出格式，第一个是总价值，括号里面的是邮票的种类，后面是相应的值。

注意：第二组数据中 1 1 算不同类型的邮票。

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <string.h>
  6 using namespace std;
  7 int Stamps[1010];
  8 struct node
  9 {
 10     int Select[5];  //存储选取的邮票的下标
 11     int type;       //类型个数
 12     int num;       //个数
 13     int Max;       //最大值
 14 }a,b;
 15 bool istie;
 16 bool flag;
 17 int n,m;
 18 int Type(node &a)   //邮票类型数量
 19 {
 20     bool vis[1010];
 21     memset(vis,false, sizeof(vis));
 22     int cnt=0;
 23     for (int i=0; i<a.num; i++)
 24     {
 25         if(!vis[a.Select[i]])
 26         {
 27             cnt++;
 28             vis[a.Select[i]]=true;
 29         }
 30     }
 31     return cnt;
 32 }
 33 int Max_num(node &a)  //邮票中最大的值
 34 {
 35     int max=-1000000;
 36     for (int i=0; i<a.num; i++)
 37     {
 38         if(Stamps[a.Select[i]]>max)
 39         {
 40             max=Stamps[a.Select[i]];
 41         }
 42     }
 43     return max;
 44 }
 45 void judege(node &a,node &b)  //判断是否符合更新数据的要求
 46 {
 47     a.type=Type(a);
 48     a.Max=Max_num(a);
 49     b.type=Type(b);
 50     b.Max=Max_num(b);
 51     if(a.num==-1||b.type>a.type || (b.type==a.type && b.num<a.num) || (b.type==a.type && a.num==b.num && a.Max<b.Max))
 52     {
 53         a=b;
 54         istie=false;
 55         return;
 56     }
 57     if((b.type==a.type && a.num==b.num && a.Max==b.Max))
 58     {
 59         istie=true;
 60     }
 61 }
 62 void dfs(int cnt,int pos)  //cnt 已组合的邮票的值，pos搜索邮票所在的下标
 63 {
 64     if(cnt==m)
 65     {
 66         flag=false;
 67         judege(a, b);
 68         return;
 69     }
 70     if(b.num>=4|| cnt>m)  //限制搜索深度
 71     {
 72         return;
 73     }
 74     for (int i=pos; i<n; i++)
 75     {
 76         b.Select[b.num]=i;
 77         b.num++;
 78         dfs(cnt+Stamps[i],i);   //可用多次，所以从上次结束的位置开始枚举
 79         b.num--;
 80     }
 81 }
 82 void Init()  //初始化
 83 {
 84     istie=false;
 85     flag=true;
 86     a.num=-1;
 87     a.Max=0;
 88     a.type=0;
 89     
 90     b.Max=0;
 91     b.num=0;
 92     b.type=0;
 93 }
 94 int main()
 95 {
 96     int x;
 97     while (scanf("%d",&x)!=EOF)
 98     {
 99         Stamps[0]=x;
100         n=1;
101         while (scanf("%d",&x) && x)
102         {
103             Stamps[n++]=x;
104         }
105         sort(Stamps, Stamps+n);  //排序
106         while (scanf("%d",&m)&& m)
107         {
108             Init();
109             dfs(0, 0);
110             printf("%d ",m);
111             if(flag)
112             {
113                 printf("---- none
");
114             }
115             else
116             {
117                 printf("(%d):",a.type);
118                 if(istie)
119                 {
120                     printf(" tie
");
121                 }
122                 else
123                 {
124                     for (int i=0; i<a.num; i++)
125                     {
126                         printf(" %d",Stamps[a.Select[i]]);
127                     }
128                     printf("
");
129                 }
130             }
131         }
132     }
133     return 0;
134 }