首页 > 编程语言 >算法之动态规划(DP)求解完全背包问题(状态转移式方程推导)

算法之动态规划(DP)求解完全背包问题(状态转移式方程推导)

时间:2023-10-06 14:23:45浏览次数:40  
标签:背包 推导 int max 01 DP 物品 dp


完全背包是01背包的进阶版。在这里补充一下代码随想录的完全背包状态转移式的推导。有兴趣的可以先看一看原版。

  1. 状态转移方程
    状态:dp[i][j] 选择前i个物品,容量为j的背包时 所选物品价值总和最大。
    状态转移:
    dp[i][j]=max(dp[i-1][j-k* v[i]]+k* w[i]) (k=0,1,2,3...) (j-k* v[i]>0)

  2. 方程优化
    dp[i][j]=max(dp[i-1][j],dp[i-1][j- v[i]]+ w[i],dp[i-1][j- 2* v[i]]+ 2* w[i],....) --->(1)
    dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j- 2* v[i]]+ w[i],dp[i-1][j- 3* v[i]]+ 2* w[i],....)
    dp[i][j-v[i]]+w[i]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j- 2* v[i]]+ 2 * w[i],dp[i-1][j- 3* v[i]]+ 3* w[i],....) --->(2)
    结合(1)(2)可得:
    dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);

  3. 对比01背包

    • dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])(01背包)
    • dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])(完全背包)

    发现了区别在下标从i-1变为i。为什么呢?
    f[i][j - v[i]] 已经将除去1个物品i时的所有最优解已经求出来了,因此在计算f[i][j]时,无需再重复计算k=2,3,4,5…时的值了。

  • 代码:
// 先遍历物品,在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

标签:背包,推导,int,max,01,DP,物品,dp
From: https://www.cnblogs.com/wryy/p/17744528.html

相关文章

  • 10.5 认识XEDParse汇编引擎
    XEDParse是一款开源的x86指令编码库,该库用于将MASM语法的汇编指令级转换为对等的机器码,并以XED格式输出,目前该库支持x86、x64平台下的汇编编码,XEDParse的特点是高效、准确、易于使用,它可以良好地处理各种类型的指令,从而更容易地确定一段程序的指令集。XEDParse库可以集成到许多不......
  • DP提高专项3
    本场比赛难度吧不大,建议开题顺序为\(T2-T1-T3\)。\(T2\)题目描述有\(n\)个高楼排成一行,每个楼有一个高度\(h_i\)。称可以从楼\(i\)跳到楼\(j\),当\(i\),\(j\)(\(i<j\))满足以下三个条件之一:\(i+1=j\)\(\max(h_{i+1},h_{i+2},\cdots,h_{j-1})<\min(h_i,h_j......
  • 【DP】ABC273F Hammer 2 题解
    ABC273F一道比较板的区间\(\text{dp}\)。先对坐标离散化,令离散化数组为\(v\)。令\(f_{i,j}\)表示能走到区间\([v_i,v_j]\)的最短路程,显然\(f\)数组初始为\(inf\)。但发现这样无法转移,可以再增加一维\(k\in\{0,1\}\),表示此时在\([v_i,v_j]\)的\(v_i/v_j\)处。......
  • 【思维】【DP】ABC298Ex Sum of Min of Length 题解
    ABC298Ex简单题。因为有\(\min\)不好做,容易想到讨论\(d(i,L)\)和\(d(i,R)\)的大小。令\(p=\text{LCA}(L,R)\),\(dep_L>dep_R,dist=dep_L+dep_R-2\timesdep_p\),\(now\)满足\(dep_L-dep_{now}=\lfloor\dfrac{dist}{2}\rfloor\)则\(L\)一定在......
  • 动态规划--DP
    动态规划动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。背包01背包每个物体只有两种可能的状态(取与不取),对应二进制中的\(0\)和\(1\),这类问题便被称为「0-1背包问题」。状态转移方程:\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})\]这......
  • 【竞赛图】【DP】ARC163D Sum of SCC 题解
    ARC163D发现这个竞赛图一定能被分为两个集合\(A\),\(B\)。满足\(\forallu\inA,v\inB\),均有\(u\tov\inE\)。答案就是划分这两个集合的方案数。证明:首先,竞赛图缩完点后一定是一条链,对强连通分量进行标号,满足编号小的强连通分量指向编号大的强连通分量。不妨令竞赛图\(G\)......
  • 【整除分块】【DP】ABC239Ex Dice Product 2 题解
    ABC239H简单题。令\(f_i\)表示乘到\(\gei\)的期望。容易得到\(f_i=\dfrac{\sum\limits_{j=1}^{n}f_{\lceil\frac{i}{j}\rceil}}{n}\)。将\(f_i\)移到同一边,去掉系数,有\(f_i=\dfrac{n\sum\limits_{j=2}^{n}f_{\lceil\frac{i}{j}\rceil}}{n-1}\)。提出\(\frac{n-1}{n......
  • 子树合并背包类型的 dp 的复杂度证明
    首先,我们发现,转移一颗子树的背包,实际上就是把该子树的根节点的所有儿子的子树背包合并,再与根节点合并。具体的,合并两颗子树的转移方程式如下:\[f(u,i)=\max\limits_{j+k=i}\{f(v_1,j)+f(v_2,k)\}\]于是有如下伪代码:dfs(u): su=1 f(u,1)=w[u] for(vinu) sv=siz......
  • 关于一类期望 dp 的公式推导
    想写但想不起来写啥......
  • Letter Picking (CF D) (区间DP, 暴力)(0,1,2 Alice 平 bob ,尽可能小,尽可能大)
     思路:区间dp(区间DP的时间复杂度不一定是n^3,可能是n^2更具题意)直接题直接区间dp,0Alice赢1平局2Bob赢(于是alice尽可能小,bob尽可能大)alice选l,bob可以选l+1,或者ralice选r,bob可选l或者r-1,看代码就行了#include<bits/stdc......