POJ10101020DFS+剪枝

之所以要写这两题的解题报告&＃xff0c;原因就是这两题是比较好的搜索题&＃xff0c;必须记录一下。

另外&＃xff0c;最近做题状态也不行&＃xff0c;看见题目后没想法&＃xff0c;然后看别人解题报告了&＃xff0c;突然发现自己想过这方面&＃xff0c;但是没深入去想&＃xff0c;然后就做不出来了。

1.POJ 1010 题意晦涩难懂。从网上找了一个稍微能说清楚的题意

题意&＃xff1a;
给出n种邮票&＃xff0c;每种邮票有自己的面值&＃xff08;面值可能重复&＃xff09;
指定m种“总面值”&＃xff0c;对每种“总面值”&＃xff0c;求解满足如下条件的组合以达到该“总面值”
&＃xff08;1&＃xff09; 所用邮票在n种中可以重复选取
&＃xff08;2&＃xff09; 所用邮票张数〈&＃xff1d;4
&＃xff08;3&＃xff09; 尽量多的使用那个不同种类的邮票 Max (Stamp Types)
&＃xff08;4&＃xff09; 若有多种方案满足&＃xff08;3&＃xff09;&＃xff0c;则选取张数最小的一种方案 Min (Stamp Num)
&＃xff08;5&＃xff09; 若有多种方案满足(3)(4),则选取“最大面额”最高的一种方案。 Max(Heightest Value)
&＃xff08;6&＃xff09; 若有多种方案满足&＃xff08;3&＃xff09;&＃xff08;4&＃xff09;&＃xff08;5&＃xff09; 则输出 “tie”1010

并且这题给的sample都还夹着注释&＃xff0c;不仔细看题还以为那些也需要输入。

说一下思路吧&＃xff0c;动态规划是最优选择&＃xff0c;但是确实不好想&＃xff0c;普遍的都是用DFS。

优化之一&＃xff1a; 每种面值的邮票最多5种即可&＃xff0c;如果有多的&＃xff0c;就不需要了。比如一下子给了1 1 1 1 1 1 1 1&＃xff0c;八个1&＃xff0c;其实只需要5个就行&＃xff0c;因为题目说了&＃xff0c;最多4个&＃xff0c;保留5个的目的就是为了多解准备的。再多也没意义。这样由于最多有25种邮票&＃xff0c;也就是数组到126就够了。

然后dfs过程中如果选择的邮票面额之和大于所需的&＃xff0c;也剪掉&＃xff0c;总数大于4的剪掉&＃xff0c;剩下的貌似就没什么了。

dfs过程中&＃xff0c;有一个中间值&＃xff0c;存储着邮票的种类&＃xff0c;总个数&＃xff0c;最大面值&＃xff0c;所选的邮票等&＃xff0c;然后有一个最终结果&＃xff0c;每次dfs出的中间值&＃xff0c;如果优于最终结果就要更新最终结果&＃xff0c;那么怎样算是tie呢&＃xff0c;就要用1个变量标记一下&＃xff0c;如果被更新了&＃xff0c;就置这个变量为1&＃xff0c;如果出现打平的&＃xff0c;就把他&＃43;&＃43;一下&＃xff0c;这样不断的覆盖这个变量即可。

另外&＃xff0c;这道题目貌似给的序列都是有序的。

/*
ID: sdj22251
PROG: subset
LANG: C&＃43;&＃43;
*/
#include
#include
#include
#include

2.poj 1020

又是一道搜索题

题目大意是给出一个大的正方形&＃xff0c;然后又给出了一群小正方形&＃xff0c;问大的正方形能不能由这些小正方形组成&＃xff0c;并且每个正方形都要用到。

思路是贪心&＃43;dfs

首先&＃xff0c;对输入的数组&＃xff0c;由于题目中说了&＃xff0c;小正方形的边长范围是1~10&＃xff0c;所以开个数组记录一下每个边长的正方形个数&＃xff0c;dfs的时候枚举就方便了。

然后用一个数组&＃xff0c;len[i]表示第i行被覆盖了len[i]列&＃xff0c;而且是左边无空隙的。

然后每次贪心找最小的len[i]&＃xff0c;因为这样的话&＃xff0c;达到最优解的可行性最大。在这个位置上&＃xff0c;看下面和右面是否有足够的位置&＃xff0c;前提是左边是填充好的&＃xff0c;所以就要求这些位置的len[i]必须都是一样的&＃xff0c;然后就枚举边长&＃xff0c;往里塞小正方形&＃xff0c;找不到解就回溯。

网上有的贪心是不正确的&＃xff0c;因为没有考虑到一些比较特别的数据&＃xff0c;而且poj的这道题数据还很弱。正确的做法应该是贪心&＃43;回溯&＃xff0c;就能保证一定要到正确的答案。

/*
ID: sdj22251
PROG: subset
LANG: C&＃43;&＃43;
*/
#include
#include
#include
#include