动态规划杂谈

[maiff]

动态规划杂谈

---

源起

为什么突然想到搞动态规划，毕设搞的分词实现vetebi算法的时候需要动态规划愣是看不懂。话说我接触动态规划挺久的但就是老是忘，就像有的刷的题我觉得还是没真正的理解，如果真正理解应该是不会忘的。

什么是动态规划

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。
而拆分问题，靠的就是状态的定义和状态转移方程的定义。

上面就是我在知乎上找到的定义，之前理解的不是很深刻，但是最近结合做题什么的，理解的还行我们直接先看一题进入状态。

每天可以做简单的任务或者难的任务，难的只有在前一天没做的时候才可以做。
dp[n] = max(dp[n-1]+list[n][0], dp[n-2]+list[n][1])

背包问题

动态规划最经典的问题就是背包问题，我找了两个参考链接1，2,需要结合起来看才能看懂。
首先动态规划可以用递归去做，而且更好理解对于初学者来说，但是不得不说有个问题。会有重复计算导致做题超时啥的。

01背包

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

for(int i = 1; i <= n; i++)  
    {  
        for(int j = 0; j <= W; j++)  
        {  
            if(j < w[i])    dp[i][j]  = dp[i-1][j];  
            else 
                dp[i][j] =  max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);  
        }  
    } 

可以像这样思考

还有个节省内存的方法

int f[w+1];     
for (int i=0; i<n; i++)  
    for (int j=w; j>=size[i]; j--)  
        f[j] = max(f[j], f[j-size[i]]+value[i]);  

case

int w[] = {1,4,1,1};
int v[] = {2,3,4,6};
// 总容量 4

过程

w:4 3 2 1
  2 2 2 2
  3
  6 6 6 4
  12 12 10 6

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

完全背包

物品不止一件
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

for (int i=0; i<n; i++)  
    for (int j=size[i]; j<=w; j++)  
        f[j] = max(f[j], f[j-size[i]]+value[i]); 

多重背包

f[i][v] = max{f[i − 1][v − k × c[i]] + k × w[i]} 0 <= k <= n[i]

#include<iostream>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
  
int Value[105];  
int Cost[105];  
int Bag[105];  
int dp[105];  
  
int main()  
{  
    int C,m,n;  
    scanf("%d",&C);  
    while(C--)  
    {  
        scanf("%d%d",&n,&m);  
        for(int i = 1; i <= m; i++)  
            scanf("%d%d%d",&Cost[i],&Value[i],&Bag[i]);  
        memset(dp,0,sizeof(dp));  
        for(int i=1; i<= m; i++)  
            for(int j=1; j<=Bag[i]; j++)  
                for(int k=n; k>=Cost[i]; k--)  
                    dp[k]=max(dp[k], dp[k-Cost[i]]+Value[i]);  
        printf("%d\n",dp[n]);  
    }  
    return 0;  
}  

上面是没经过优化的多重背包，一个一个的考虑，经过优化的用二进制进行分解然后转化为01背包就ok。

#include <iostream>  
using namespace std;  
int main()  
{  
    int nCase,Limit,nKind,i,j,k,  v[111],w[111],c[111],dp[111];  
    //v[]存价值，w[]存尺寸，c[]存件数  
    //在本题中，价值是米的重量，尺寸是米的价格  
    int count,Value[1111],size[1111];  
    //count存储分解完后的物品总数  
    //Value存储分解完后每件物品的价值  
    //size存储分解完后每件物品的尺寸  
    cin>>nCase;  
    while(nCase--)  
    {  
        count=0;  
        cin>>Limit>>nKind;  
        for(i=0; i<nKind; i++)  
        {  
            cin>>w[i]>>v[i]>>c[i];  
            //对该种类的c[i]件物品进行二进制分解  
            for(j=1; j<=c[i]; j<<=1)  
            {  
                //<<左移1位，相当于乘2  
                Value[count]=j*v[i];  
                size[count++]=j*w[i];  
                c[i]-=j;  
            }  
            if(c[i]>0)  
            {  
                Value[count]=c[i]*v[i];  
                size[count++]=c[i]*w[i];  
            }  
        }  
        //经过上面对每一种物品的分解，  
        //现在Value[]存的就是分解后的物品价值  
        //size[]存的就是分解后的物品尺寸  
        //count就相当于原来的n  
        //下面就直接用01背包算法来解  
        memset(dp,0,sizeof(dp));  
        for(i=0; i<count; i++)  
            for(j=Limit; j>=size[i]; j--)  
                if(dp[j]<dp[j-size[i]]+Value[i])  
                    dp[j]=dp[j-size[i]]+Value[i];  
  
        cout<<dp[Limit]<<endl;  
    }  
    return 0;  
}  

之后准备把母函数加上去的，但是这个内容真的太多了，等下一篇再加吧。