妙用记忆化搜索解题例析
因为搜索太慢，所以超时了；因为动规太难，所以不编了。那么，这道题目就这样完了？如果可以，那么，我们就试试记忆化搜索。
                                                                       
题1
0/1 背包(package.pas)
【问题描述】
一个旅行者有一个最多能用 m 公斤的背包，现在有 n 件物品，它们的重量分别是 W1， W2，...,Wn,它们的价值分别为 C1,C2,...,Cn。若每种物品只有一件，求旅行者能获得最 大总价值。
【输入格】
第一行：两个整数，M(背包容量，M<=200)和 N(物品数量，N<=30)； 第 2..N+1 行：每行二个整数 Wi,Ci，表示每个物品的重量和价值。
【输出格式】 仅一行，一个数，表示最大总价值。
【样例输入】package.in
    10 4
2     1
3     3
4     5
7     9
【样例输出】package.out
12
【问题分析】
题目很经典，就是给你物品的重量和价值，叫你求最多用M单位的重量能获得的物品最大总价值。
【算法分析】
对于背包问题的动态转移方程和动规程序段大家都不陌生了：
for i:=1 to n do
for j:=m downto a[i] do
if f[j-a[i]]+b[i]>f[j] then f[j]:=f[j-a[i]]+b[i];
(n代表物品数，m代表最大重量,a数组代表物品重量，b数组代表物品价值，f数组代表每个重量所能取得的最大价值)
那么，其实这道题目也可以用记忆化搜索来编，它的形式或许就是我们原本搜索的算法（
时间复杂度为O（2^n），效率低下）的基础上加上2句语句就行了，但是，他的效率却与动规不相上下。
原本我们的搜索算法递归的变量是：还剩下重量j（也就是用了(m-j)的重量）并且还剩下前i个物品（也就是搜了(n-i)个物品（有的要了，有的没要））的价值，并且每次搜索分两种情况：1、此种物品不取，2、取此种物品（前提是剩下的重量要够取），然后我们在这两者间选最优值，即能获得的物品最大总价值。
那么在搜索的过程中，我们会重复计算I,j分别相同下的值。怎样优化呢？其实，现在只要用一个数组f[I,j]来存放此时搜索出来的I,j值（因为这个值保证最优，所以不需要再计算了），开始都赋值成-1，每次算相应的I,j的时候就记录下来，如果下次搜索时碰到一样的I,j的值，就不需要在重复求了。不要小看这一个“看似”不起眼的小小优化，其实此时我们的记忆化搜索的速度已经相当于动规了，而且数据小，可能还要快（因为动规要将每个重量所能取得的最大价值都算出来，而搜索只要算一部分）。
【参考程序】（记忆化搜索）
var f:array[0..30,0..10000] of longint;
    w,v:array[1..30] of longint;
    n,m,i,j:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function get(i,j:longint):longint;  {还剩下重量j并且还剩下前i个物品的价值}
var t:longint;
begin
if (i<1) then exit(0);            {如果此时已没有物品可取，就返回0}
if f[i,j]<0 then                  {若对应的I,j没有求过}
begin
if j<w[i] then t:=get(i-1,j)        {取物品的重量不够，就不能取}
          else t:=max(get(i-1,j),get(i-1,j-w[i])+v[i]);
{够，就在两者中选其最优值}
f[i,j]:=t;                        {记录算出的值}
end;
exit(f[i,j]);                      {返回最优值}
end;
begin
assign(input,'package.in');
assign(output,'package.out');
reset(input);rewrite(output);
readln(m,n);
for i:=1 to n do readln(w[i],v[i]);
fillchar(f,sizeof(f),255);          {赋值成-1}
writeln(get(n,m));              {记忆化搜索}
close(input);close(output);
end.
【参考程序】（动规）
var n,m,i,j:longint;
    a,b:array[1..30] of longint;
    f:array[0..200] of longint;
begin
assign(input,'package.in');
assign(output,'package.out');
reset(input);rewrite(output);
readln(m,n);
for i:=1 to n do readln(a[i],b[i]);
for i:=1 to n do
for j:=m downto a[i] do
if f[j-a[i]]+b[i]>f[j] then f[j]:=f[j-a[i]]+b[i];
writeln(f[m]);
close(input);close(output);
end.
本题小结：
其实01背包这样经典的题目也可以用记忆化搜索来做，虽然看起好像搜索烦了点，但是，这种形式是值得推荐的。
题2
最小步数(steps.pas)
从起点到终点有N步，如果“走”第K步，将会得到A[K]元钱，A[K]可能为负数。你也可以花100元钱“跳过”当前的这一步，即不会得到A[K]。但是任何时刻身上的钱都必须是非负的。开始时，你身上共有0元。给定数组A，求在能到达终点的情况下最小需要走过（即不是用100元钱跳过）的步数。注意：最后一步必须走，不能选择跳过。
输入格式(steps.in)：
共有两行。
第一行为整数N（0<=N<=100）。
第二行有N个整数，第K个数为A[K]，-10000<=A[K]<=10000，。
输出格式(steps.out)：
一个整数，表示需要走的最少步数。若无法走到终点，输出-1。
样例：
输入
6
30 30 30 30 30 30
输出
5
【问题分析】
题目等于是一共有N步让你走，你可以花100元钱不走，或者走，并且身上的钱都必须是非负的（就是不能欠）。
对于问题的第K步必须理解透彻，否则，很容易引起编程序时的错误算法。
【算法分析】
看到每一步只有两种情况：走或跳（不走），大家肯定马上就会想到搜索。从第一步开始，能跳就跳，能走就走，反复搜索，达到第N步了，因为不能跳，就判断一下走过最后一步后钱是否是非负的，是的话，记录最少需要走的最少步数，直至搜索结束。不过，看一下数据范围：N（0<=N<=100），而我们的程序时间复杂度大约是（2^n），极限数据根本吃不消。
先从小剪枝入手，因为求的“最少”步数，所以我们在搜索时，若此时的需要走的最少步数已大于等于目前求出来的走完后需要走的最少步数，就直接退出此时的搜索。可是这个优化毕竟还是很弱，对于一些很特殊的或者说是很强的数据，优化的力度毕竟是有限的。
仔细一想，由于题目最后让我们求的是最少步数，即最优值，比较明显，类似于背包问题
的状态，我们可以把此时的步数和钱数作为状态来优化我们的搜索。即在搜索时用数组f[I,j]来记录走到第i步用了j元钱所需要走的最少步数（数组的值）。可是，这样还是没有做到最优，我们可以换一个角度，把j的值用来代表所需要走的最少步数，把数组的值记录为最大钱数（因为钱越多越好，可以一直跳啊跳），这样也可以求出最后的结果。这样，我们就可以再加一个强剪枝了，此时的搜索便成了记忆化搜索，对付一般的N（0<=N<=100）的数据是绰绰有余的了。
注意：
1、最后一步必须走，不能选择跳过。题目里也说了，其实我们只要直接判断最后一步所走完的钱加上后是否是非负数就行了。
2、得到A[K]元钱有可能是负数。所以也要加判断。
3、若无法走到终点，输出-1。别忘记了。
【参考程序】（搜索）
var n,i,min:longint;{min:最优值}
    a:array[1..100] of longint;
f:array[1..100,0..100] of longint;
{记录走到第ifunction怎么记忆步所需要j步最少步数剩下的最大钱数}
procedure search(i,j,s:longint);{搜索,到达当前第i步，需要走s步最少步数所花j元钱}
begin
if (s+1>=min) or (j<=f[i,s]) then exit;
{ (s+1>=min)是弱剪枝,(j<=f[i,s])是强剪枝（记忆化搜索）}
f[i,s]:=j;{记录}
if (i=n) then begin if (j+a[i]>=0) and (s+1<min) then min:=s+1;end
{已到最后一步，记录}
        else
begin
if (j-100>=0) then search(i+1,j-100,s);      {跳}
if (j+a[i]>=0) then search(i+1,j+a[i],s+1);  {走}
end;
end;
begin
assign(input,'steps.in');
assign(output,'steps.out');
reset(input);rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);readln;
min:=maxlongint;{初始化}
fillchar(f,sizeof(f),255);{钱不可能是负的，所以设置成-1}
search(1,0,0);{记忆化搜索}
if min=maxlongint then writeln('-1')    {不能走到终点}
                  else writeln(min);  {可以走到终点}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。