转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1311305814
大致题意：
题意比较难懂。大致如下：
第一行数字是邮票的面值，每一个数字就是一个不同的种类，哪怕面值相同。以0结束。
第二行数字是顾客所需要的邮票总面值。每个数字就是一个顾客的需求，以0结束。
每两行是一组case。以EOF结束输入。
顾客是集邮爱好者，所以你必须尽可能的给他不同种类的邮票。
但是一位顾客最多只能拿4张邮票。
显然，我们拥有的邮票就是第一行中的数据。
解题思路：
DFS寻找所有的解，再逐一比较寻找最优解，剪枝是关键。
关于tie。
满足顾客需求的解就是可行解。
邮票种类最多的可行解为最优。
如果存在两个以上的最优解的邮票种类是一样的，张数最少的更优
张数也一样的话，这些最优解中最大面值较大的更优。
若邮票种类、张数、最大面值三者都分别相同，则认为这些最优解相同，输出tie。
没有解就是none。
做法大致有三种。
可以去参考这位牛人的三种方法：http://blog.csdn.net/cugbliang/article/details/2742242
1、枚举。反正最多拿4张，可以4重循环暴搜最优解。
2、DFS。每次搜索后，如果有解，更新最优解，关键在剪枝。
3、三维DP。这个没怎么研究，不太懂……参考上面的网址吧。。
我用的是第二种DFS
剪枝：
1、最多拿四张邮票，如果同一面值的邮票种类超过5，以5计算。
为什么不以4计算呢？因为tie
2、若DFS的深度超过了4，那么就返回。（最多四张邮票）
3、技巧剪枝：
先对输入的邮票按面值升序排序，DFS到面值k时，不再搜索面值<k的邮票。
同时排序也是为了保证DFS的最优解的邮票种类最多。
Source修正：
http://www.cs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/1998/ContestProblems/
1 //Memory Time
2 // 228K 0MS
3
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 const int size=26;
9
10 int value[size]; //第i种邮票面值value[i]
11 int pv; //value[]指针
12 int time[size]; //标记第i种邮票被分配过的次数
13
14 bool flag; //标记是否已经出现过解
15 bool flag_tie; //标记是否为tie
16 int solve[6]; //solve[0]:邮票张数 solve[5]:邮票种数 solve[1..4]:持有的邮票面值，0表示不持有
17 int BestSolve[6]; //最优解
18
19 void dfs(int need,int num,int type,int pre); //need:总面值 num:邮票张数 type:邮票种数
20 int max4(int* s); //返回s[1..4] 4个数中的最大值
21 void best(int num,int type); //更新最优解
22
23 int main(void)
24 {
25 while(true)
26 {
27 pv=0;
28 int type[size]={0}; //面值为i的邮票的种数type[i]
29
30 int tmp;
31 while(true)
32 {
33 if(scanf("%d",&tmp)==EOF)
34 exit(0);
35 if(tmp==0)
36 break;
37
38 if(type[ tmp ]<5) //剪枝，同面额的邮票种类超过5，则按5计算
39 {
40 type[ tmp ]++;
41 value[pv++]=tmp;
42 }
43 }
44 sort(value,value+pv); //要使分配的邮票的种类尽可能多
45 //只需在搜索前把邮票面值升序排序，从最小面额开始搜索
46
47 int need; //顾客需求
48 while(cin>>need && need)
49 {
50 flag=false;
51 flag_tie=false;
52 memset(solve,0,sizeof(solve));
53 memset(BestSolve,0,sizeof(BestSolve));
54 memset(time,0,sizeof(time));
55
56 /*Search*/
57
58 dfs(need,0,0,0);
59
60 /*Output*/
61
62 cout<<need;
63 if(BestSolve[0]==0)
64 cout<<" ---- none"<<endl;
65 else
66 {
67 cout<<" ("<<BestSolve[5]<<"):";
68
69 if(flag_tie)
70 cout<<" tie"<<endl;
71 else
72 {
73 sort(BestSolve+1,BestSolve+5);
74 for(int i=1;i<=4;i++)
75 {
76 if(BestSolve[i]==0)
77 continue;
78 cout<<' '<<BestSolve[i];
79 }
80 cout<<endl;
81 }
82 }
83 }
84 }
85 return 0;
86 }
87
88 void dfs(int need,int num,int type,int pre) //need:总面值 num:邮票张数 type:邮票种数
89 {
90 if(num==5) //剪枝，顾客持有邮票张数不超过4
91 return;
92
93 if(need==0)
94 {
95 if(!flag)
96 {
97 if(type==BestSolve[5]) //最优解的种类type相同
98 {
99 if(num==BestSolve[0]) //最优解的张数num相同
100 {
101 int Maxs=max4(solve); //solve的最大面值
102 int MaxBs=max4(BestSolve); //BestSolve的最大面值
103
104 if(Maxs==MaxBs) //存在多个最优解
105 flag_tie=true;
106 else if(Maxs>MaxBs) //种类、张数都相同的情况下，最大面值较大的解优先
107 {
108 flag_tie=false;
109 best(num,type);
110 }
111 }
112 else if(num<BestSolve[0]) //种类相同情况下，张数少的解优先
113 {
114 flag_tie=false;
115 best(num,type);
116 }
117 }
118 else if(type>BestSolve[5]) //种类多的解优先
119 {
120 flag_tie=false;
121 best(num,type);
122 }
123 }
124 else
125 {
126 flag=true;
127 best(num,type);
128 }
129
130 return;
131 }
132
133 for(int i=pre;i<pv;i++) //i=pre 剪枝，不重复搜索比当前面值小的邮票，同时避免错误的tie
134 {
135 if(need>=value[i])
136 {
137 solve[num+1]=value[i];
138
139 if(time[i]!=0)
140 {
141 time[i]++;
142 dfs(need-value[i],num+1,type,i);
143 }
144 else
145 {
146 time[i]++;
147 dfs(need-value[i],num+1,type+1,i);
148 }
149
150 solve[num+1]=0; //回溯
151 time[i]--;
152 }
153 else
154 return; //value已排序
155 }
156
157 return;
158 }
159
160 int max4(int* s) //返回s[1..4] 4个数中的最大值
161 {
162 int a=s[1]>s[2]?s[1]:s[2];
163 int b=s[3]>s[4]?s[3]:s[4];
164
165 return a>b?a:b;
166 }
167
168 void best(int num,int type) //更新最优解
169 {
170 BestSolve[0]=num;
171 BestSolve[5]=type;
172
173 for(int k=1;k<=4;k++)
174 BestSolve[k]=solve[k];
175 return;
176 }
1 2 3 0
7 4 0
1 1 0
6 2 3 0
1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0
2 8 0
1 2 3 4 5 6 7 8 9 10 0
2 5 10 20 33 0
1 1 6 0
4 5 0
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
2 (2): 1 1
8 (4): tie
2 (1): 2
5 (2): 1 4
10 (4): 1 2 3 4
20 (4): tie
33 (4): 6 8 9 10
4 (2): tie
5 ---- none