01背包笔记 51nod1085

再次分析一下这个非常经典的动态规划吧~~

首先用w[]数组存下每个的重量，v[]数组存下每个的价值，package表示背包的能装下的最大重量。

这里我们把子状态参数设为背包重量和处理的物品序号数。

首先说一下递归做法。

定义F(i,L)是背包容量为L，处理到第i个物品时背包中的最大价值。

那么这个状态能从前哪几个状态得到呢？

1.由于容量不够，没有拿第i个物品，从F( i-1，L）这个状态转化过来，总价值不变。

2.容量足够，拿了标号为i的物品，注意这次是从从F（i-1，L-w[i]）这个状态转化过来，与原状态相比总价值增加了w[i]。

一共就这个两种状态能转化到F(i,L)。

显然我们要取这两个状态的最大值为F(i,L)。

最终想要到第n个物品，背包的容量是L，即（F(n,L)）。

那么递归过程如下：

//这个只是思路啊，其实递归过程本身就是为了帮我们理清动态规划的。

int F(int i,int L)//处理到第i件物品,剩余的空间为L,其返回值是这个状态的能盛下的最大价值。
{
    if(i==0)    return 0;

    int r1=-1,r2=-1;
    if(L>=w[i])//(背包剩余空间可以放下物品 i )
    {
        r1=F(i-1,L-w[i])//第i件物品放入所能得到的价值
    }

    r2=F(i-1,L)//第i件物品不放所得到的价值

    return max(r1,r2);//取最大的
}

于是噼里啪啦递归下去，到达边界。

边界是 F(0,l)=0 ;

显然有好多哦是被重复计算的啦~

那么我们来对他动态规划。

从哪儿到哪儿？ 首先我们的状态由是背包的容量和剩下物品数决定的。

本来递归时候是容量从大到小，物品数有少到多进行的。

那么就逆着来啦~

边界是 F(0,L)=0 ，初始状态。

处理顺序从第1个到第n个，