Share and review my study process.

引论

个人理解动态规划应该是一种设计技巧，和分治法类似，但DP更关心子问题的重叠。

动态规划是一种在各个不同大小(size)的子问题的优化值之间建立递归关系并求解的过程.

能使用动态规划求解的问题必须满足优化原理：

优化解包含的子问题的解也是最优的

即可利用优化原理，使用枚举法建立不同长度子问题优化值之间的递归关系—动态规划方程。

注意，动态规划算法得出的解为精确解，子问题的数目决定了该算法的复杂度.

Ps: 尽量不要用递归

经典的0/1背包

给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。

问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

  

在学习DP算法之前，我们面对01背包问题有的思路就是贪心和穷举：

不管是对价值排序还是对价值密度排序，只是改变了贪心策略，但还是贪心算法，也就意味着我们只能求解一个近似解，无法得到精确解。

而穷举法的开销太大了，在很多情况下复杂且不适用。

既然贪心法在理论上是无法得到精确解的，那我们能否在穷举的基础上进行优化呢？

来一个具体的例子

n=5,c=10,w=[2,2,6,5,4],p=[6,3,5,4,6].

可知此时的优化解为(1,1,0,0,1),即装1,2,5物品

想要用DP算法，首先要判断问题是否满足优化原理

即优化解包含的子问题的解是否最优。

当我们先装物品1时。

物品1装入，子问题为n=4,c’=c-2(物品1的重量),物品为2,3,4,5

可以看到子问题的优化解为(1,0,0,1)

与优化解相同

可以得知01背包问题满足优化原理。

DP的思路分析

面对n个物品，我们并不知道该拿哪几个才是最优解，那么就使用计算机最擅长的技能：计算(遍历)

只不过我们会对遍历进行一些操作

设函数 f(i,y)表示当背包容量为y时，面对 i，i+1,…，n物品时的最优解。

可以知道f(1,c)就是我们最终要求的答案

求 f(1,c)遇到的第一个问题就是物品1拿不拿？

答案是：不知道。  但我们可以根据子问题推出来物品1拿不拿。

f(1,c)=max{f(2,c), f(2,c-w1)+p1}

这样我们的思路就出来了：建立一个父问题与子问题递归式。即在最后一个物品时返回两种情况：拿或不拿。再一路返回到第一种情况，判断物品1拿不拿。

下面是递归算法和非递归算法

递归法

//递归算法
#include <iostream>
#include <algorithm>

using namespace std;

int content;
int num_things;

int weightt[101];
int value[101];
int dp(int thing,int content)
{
    int dp1=0;
    int dp2;
    if(thing==num_things-1)
    {
        if(content<weightt[num_things-1])
        return 0;
        else
        {
            return value[num_things-1];
        }
        
    }
    if(content>=weightt[thing])
    dp1=dp(thing+1,content-weightt[thing])+value[thing];
    dp2=dp(thing+1,content);
    return max(dp1,dp2);
}
int main()
{
    cin>>content>>num_things;
    for(int i=0;i<num_things;i++)
    cin>>weightt[i];
    for(int i=0;i<num_things;i++)
    cin>>value[i];
    cout<<dp(0,content)<<endl;
    return 0;
}

由于递归算法开销很大，所以我们使用元组法来实现DP

当W为整数时 迭代法

/*Easy code using martix, and all need to do is initial it*/
#include <iostream>
#include <algorithm>

using namespace std;

const int Maxnumber=100;
const int Maxvalue=100;
int f[Maxnumber][Maxvalue];

void knapsack(int p[],int w[],int c,int n)
{
    //initial f[n][i]
    for(int y=0;y<w[n-1]-1;y++)
    f[n-1][y]=0;
    for(int y=w[n-1]-1;y<c;y++)
    f[n-1][y]=p[n-1];
    for(int i=n-2;i>0;i--){
        for(int j=0;j<w[i]-1;j++)
        f[i][j]=f[i+1][j];
        for(int j=w[i]-1;j<c;j++)
        f[i][j]=max(f[i+1][j],f[i+1][j-w[i]]+p[i]);
    }
    f[0][c-1]=f[1][c-1];
    if(c>=w[0])
    f[0][c-1]=max(f[1][c-1],f[1][c-1-w[0]]+p[0]);
}

int main()
{
    int p[Maxnumber];
    int w[Maxnumber];
    int n;
    int c;
    cout<<"input the number of things and content of package"<<endl;
    cin>>n>>c;
    cout<<"input value of each thing\n";
    for(int i=0;i<n;i++)
    cin>>p[i];
    cout<<"input weight of each thing\n";
    for(int i=0;i<n;i++)
    cin>>w[i];
    knapsack(p,w,c,n);
    cout<<f[0][c-1]<<endl;
    for(int i=n-1;i>0;i--){
        for(int j=0;j<c;j++)
        cout<<f[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

元组法

仔细回想我们的01背包问题，是否有这样一个感觉，效益值=f(i,y)是一个分段函数，且每一段都是效益值不变的水平直线。

那么我们只要记住分段函数的跳跃点，是否就可以对输入的每种情况进行还原(和数据结构中稀疏矩阵的存储相似)

 

由于f(i, y)=max{ f(i+1,y),f(i+1,y-wi)+pi }

设f(i,y)对应元组P(i), f(i+1,y-wi)+pi对应元组Q

我们想要得到的是P(i)，所以我们需要求P(i+1)和Q。

由于f(i+1,y-wi)+pi可看作f(i+1,y)向右向上平移，所以P中每个元组(a,b)对应Q中的(a+wi,b+pi)

  

求出P(i+1)和Q后，使用类似于merge排序的方法把两个元组中的点合并

合并规则：

合并时使用以下支配(选优)规则:

设(a,b)和(u,v)是来自P(i+1)和Q的元组,若a≥u且b＜v,则称(a,b)受(u,v) 支配. 因为

(a,b)代表以容量a得到效益值b的方案,

而(u,v)代表以较少的容量u得到较大效益值v的装包方案.

(可以想象为两个分段函数一直取x相等时二者y值最大的一段)

 

得到P(2)后我们可以不求P(1)

直接利用w1和P(2)来求出满足w1+w<C的最后一个元组（w,v）

将v+p1与原来P(2)中最后一个满足条件的效益值比较，取最大的那个。