来自dp的拷打——背包

wjyppm1403 · 2024-10-06 15:19:00 · 闲话

DP 拷打动态规划第一章

大丈夫生居天地间，岂能郁郁久居于贪心之下！

0.前言

引用一下： 用贪心算法的问题 是“目光短浅”，不一定可以站在全局的角度来统筹决策，可能会出现结果并不是全局最佳的； 而使用枚举搜索算法，虽然可以遍历所有的可能，但如果数据量稍大，就可能超时。这个时候可 以考虑使用动态规划解决这些问题。

要用贪心，前提是要证明该问题是无后效性，第一层含义是，在推导后面阶段状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性

还有就是记忆化搜索=动态规划，但区别在于动态规划的性能其实平均下来比记忆化搜索要高，对于记忆化搜索的递归方式与动态规划转移方程本质上是一致的

1.线性动态规划

具有线性阶段划分的动态规划方法统称为线性动态规划，简称为线性 DP

2. 01背包问题

已知条件有第 i 个物品的重量 w_{i} ，价值 v_{i } ，以及背包的总容量 W ,每个物品只能装一次，求价格的最大值 v_{max}

特点：每个物品只能选一次，要么选（1）要么不选（0）

考虑转移。假设当前已经处理好了前 i-1 个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 f_{i-1,j} ；当其放入背包时，背包的剩余容量会减小 w_{i} ，背包中物品的总价值会增大 v_{i} ，故这种情况的最大价值为 f_{i-1,j-w_{i}}+v_{i} 。

这样下来一步一步推，从1一步一步递推下来那么最终的答案即为 f_{n,v}

记忆化搜索版本：

int t,m,ans=INT_MIN;
struct cy
{
    int ti,p;
}c[114];
//这里time可以理解为消耗的容量
//t为上文的w
//这里用的代码是P1048，01背包模板题
int vis[114][1145];
int dfs(int pos,int time){
    if(vis[pos][time]){
        //计算过？ok！
        return vis[pos][time];
    }
    //超边界喽
    if(pos>m||time>=t) return 0;

    //d1是不选，d2是选的情况（前提是背包还够）
    int d1=dfs(pos+1,time);
    int d2=INT_MIN;
    if(time+c[pos].ti<=t){
      //一眼鉴定为fn[i-1][j-a[i].w]+a[i].value
      //但是我是顺推所以这里time是累计放了多少
      d2=dfs(pos+1,time+c[pos].ti)+c[pos].p;
    }
//记录一下
    vis[pos][time]=max(d2,d1);
    return vis[pos][time];
}

dfs(1,0)

DP版本：

    for(int i=1;i<=m;i++){
        for(int j=1;j<=t;j++){
            if(j<a[i].w){//哎选不了就不选了
                fn[i][j]=fn[i-1][j];
            }else{//我看看是选好还是不选好呢
                fn[i][j]=max(fn[i-1][j],fn[i-1][j-a[i].w]+a[i].value);
            }
        }
    }

照应前言，可以直观看出记忆化搜索与动态规划之间的联系，搜索的递归方式=dp转移方程

缺点是啥， MLE ，很难受，空间瞬间爆炸

这里用到一个叫滚动数组的方法，我们考虑dp转移方程，我们发现对于当前状态只有上一个状态（即f_{i-1,j}） 那么我们可以舍去第一维的信息。这时候，每一次循环我们读取f_{j}的时候读取到的信息相当于二维数组形式下的f_{i-1,j}，通过这样我们就舍去了第一维，减小了空间。

滚动数组这种思想方式是通过观察DP方程来确定哪些数据是必要的，哪些可以被抛弃。一旦确定了这种关系，就可以在写代码时只存储那些必要的数据，大大减少空间复杂度，但要注意时间复杂度滚动数组不能优化，甚至可能会增大时间复杂度，要在刷题中不断积累经验

（滚动数组不过只是原地tp罢了，和时间复杂度有啥关系）

降低空间复杂度的时候，如果降维优化不可行，可以试试滚动数组，会有奇效。

优化后的转移方程式

时间复杂度滚动数组优化不太明显，仍为O(nm)

dp[0]=0;
for(int i=1;i<=m;i++){
    for(int j=t;j>=1;j--){
        if(j>=tim[i]){
            dp[j]=max(dp[j-tim[i]]+price[i],dp[j]);
        }
    }
}

3.完全背包

区别01在于其每个物品有无限个或可以取无限次，也是要求最大总价值

上来直接上暴力，多个枚举取得次数，由\frac{V}{v[i]}求得次数，这种方式就是一步一步尝试，时间复杂度O(n*V*sum(k))其中sum(k)代表尝试的次数总和，显然直接爆炸不可接受，空间复杂度O(n*V)

MLE+TLE，怎么办？

考虑一下贪心+DP套餐，我们可以把体积大于V的直接舍去，同体积拿最大价值，但这样优化复杂度还是会TLE

将完全背包转化为01背包来做

还是滚动数组约第一维

//f[i]表示当前体积为i的情况下，背包的最大价值是多少
for(int i = 1; i <= n; ++i)
    for(int j = v[i];j <= c; ++j)  //这里与01背包不同的地方是01背包是逆序枚举，完全背包是正序枚举
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout<<dp[c]<<endl;

ok我们发现了这里居然是正序枚举j，01居然是是倒叙枚举，给个链接看看文章吧 跳转

4.多重背包

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 k_i 个，而非一个