北大poj解题报告 1010 stamps
STAMPS
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 4537 Accepted: 1216
Description
Have you done any Philately lately?
You have been hired by the Ruritanian Postal Service (RPS) to design their new postage software. The software allocates stamps to customers based on customer needs and the denominations that are currently in stock.
Ruritania is filled with people who correspond with stamp collectors. As a service to these people, the RPS asks that all stamp allocations have the maximum number of different types of stamps in it. In fact, the RPS has been known to issue several stamps of the same denomination in order to please customers (these count as different types, even though they are the same denomination). The maximum number of different types of stamps issued at any time is twenty-five.
To save money, the RPS would like to issue as few duplicate stamps as possible (given the constraint that they want to issue as many different types). Further, the RPS won't sell more than four stamps at a time.
Input
The input for your program will be pairs of positive integer sequences, consisting of two lines, alternating until end-of-file. The first sequence are the available values of stamps, while the second sequence is a series of customer requests. For example:
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Note: the comments in this example are *not* part of the data file; data files contain only integers.
Output
For each customer, you should print the "best" combination that is exactly equal to the customer's needs, with a maximum of four stamps. If no such combination exists, print "none".
The "best" combination is defined as the maximum number of different stamp types. In case of a tie, the combination with the fewest total stamps is best. If still tied, the set with the highest single-value stamp is best. If there is still a tie, print "tie".
For the sample input file, the output should be:
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
That is, you should print the customer request, the number of types sold and the actual stamps. In case of no legal allocation, the line should look like it does in the example, with four hyphens after a space. In the case of a tie, still print the number of types but do not print the allocation (again, as in the example).Don't print extra blank at the end of each line.
Sample Input
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Sample Output
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
Source
Pacific Northwest 1998
问题重述:
给出n种邮票，每种邮票有自己的面值（面值可能重复）
指定m种“总面值”，对每种“总面值”，求解满足如下条件的组合以达到该“总面值”
（1） 所用邮票在n种中可以重复选取
（2） 所用邮票张数〈＝4
（3） 尽量多的适应那个不同总类的邮票 Max (Stamp Types)
（4） 若有多种方案满足（3），则选取张数最小的一种方案 Min (Stamp Num)
（5） 若有多种方案满足(3)(4),则选取“最大面额”最高的一种方案。 Max(Heightest Value)
（6） 若有多种方案满足（3）（4）（5） 则输出 “tie”
题目分析:
(1) 算法定位:
从题目的条件可知,此题必须遍求所有方案以求解,因此采用搜索的方法是非常合理的,因为题目带由一定的递推性,也可以尝试动态规划的方法.
(2) 问题优化与简化
对于搜索型题目,关键的优化就是减少重复计算,本题可由3方面的简化,避免重复性计算.
(1) 对于面额相等的邮票,可以限制在1~5张,多余的可以不处理,例如这样的输入:
1 1 1 1 1 1 1 1 0 8个1
4 0
可以简化成为:
1 1 1 1 1 0 5个1
4 0
他们的解是相同的
(2) 搜索求解时约定, 后一张邮票面额>=前面张邮票的面额,即如下的6种情况:
1 2 3 2 3 1 3 12 1 3 2 3 2 1 2 1 3
只需搜索判断一种,即 1 2 3 的情况
(3) 对于给定的n种邮票,遍历4张邮票的所有可达“总面额”的解，当m种指定面额给出，只需插标输出即可，不需要重复m次类似的搜索。（因为m次的搜索中，很多是重复计算的）
（3）算法介绍
（1） 搜索方法一： （base on 史诗’s program）
主要思路：
4重循环，枚举所有可能，依据题目条件保留最优解。
For(i=1;i<=total_stamps;i++)
For(j=i;j<=total_stamps;j++)
For(k=j;k<=total_stamps;k++)
For(l=k;l<=total_stamps;l++)
{
更新最优解
}
优化：
使用优化方案（1）（2）， 修改后可以加上优化方案（3）
评价：
编程复杂度低，代码少，运行时空效率高，比赛时候推荐使用
但是扩展性受限制，若题目给的是任一k张而不是4,则必须大量修改代码
（2） 搜索方法二： （base on hawking’s program）
主要思路：
递归深度搜索，遍历所有k张邮票的可达面额的解，保留每种面额的最优
解，查表输出指定面额的解，并给定k=4,即为题目要求的情况。
Void Solve(int deep)
{
更新当前方案所达面值的最优解
if (deep>4) return;
for(int s=now[deep-1];s<=total_stamp;s++)
{
now[deep]=s;
solve(deep+1);
}
}
优化：
使用优化方案（1）（2）（3）进行截枝
评价：
深度搜索的经典模板程序，推荐学习，几乎所有的搜索都可以套用的模板
编程复杂度中，运行时空效率高，通用性强一些，但代码可能稍为多一些
（3） 动态规划： (base on my program)
主要思路：
定义：int anstype[k][j] 表示：
用前k种邮票,选i张，达到面额为j，最多用多少种不同的类型邮票。
定义：bool tied[k][j] ：
k,i,j 定义如上，tied 表示 anstype[k][j] 的最优值是否有多种方案.即同时满足题目的条件（3）（4）时是否多种
定义：bool anstied[k][j] :
由于 tied 限制不够强,必须多一个anstied 表示同时满足条件(3)(4)(5)是否有多种方案
递推关系：
(1)
anstype[k][j]=Max{anstype[k-1][i-w][j-w*value[k]]+1} 1<=w<=4, i-w>0, j-w*value[k]>=0
(2)
在anstype 的更新最大值的同时，可以判断，若某个w 使得
anstype[k][j]==anstype[k-1][i-w][j-w*value[k]]+1 则
tied[k][j]=ture;
anstype[k][j]<anstype[k-1][i-w][j-w*value[k]]+1 则
tied[k][j]=false
(3)
至于anstied 可以这样求得：
anstype[k][j]<anstype[k-1][i-w][j-w*value[k]]+1时
anstied[k][j]=tied[k-1][i-w][j-w*value[k]]
anstype[k][j]==anstype[k-1][i-w][j-w*value[k]]+1时
anstied=true;
主要优化：
使用优化方案（1）（2）（3）
空间优化，由于[k][j]只与[k-1][j]有关，所以只需2维数据[j]就可以了
这是动态规划最常用的空间优化，另外的一些是压缩存储技巧，主要的是用位运算存储，本题没有用上，不过以后有些题目会常用。
评价：
编程复杂度 中，运行时间少，可以承受大规模数据，规模可扩展，
但是空间要求量大，必须使用压缩技巧，这样编程复杂度会增大，推荐研究算法用，比赛不用
总结：
类似本题的问题很多，光stamps问题多年来就一直存在各种变种，sticks问题与本体类似，通用的算法都是搜索，练熟搜索模板是基础，简化问题、掌握剪枝技巧是解题关键。某些特殊问题可以用动态规划，但是并不是所有的都可以，例如sticks我试过是不能用动态规划的，而且比赛时候，思考会浪费时间，所以推荐比赛时用搜索。（不排除某些题目用搜索通过不了的大数据，必须用动态规划解决，所以要估计好时间空间，选用稳妥的算法）