动态规划DP--背包问题

2024-09-05 19:36
文章标签 动态 规划 问题 dp 背包

本文主要是介绍动态规划DP--背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 0-1背包问题 -- 问题定义
    • 动态规划解法
    • 代码
    • 题目:分割等和子集
    • 题解

0-1背包问题 – 问题定义

在 0-1 背包问题中,给定一个背包的最大容量 W,以及 n 个物品,每个物品有两个属性:

  • 重量:第 i 个物品的重量为 wt[i]
  • 价值:第 i 个物品的价值为 val[i]

目标是选择若干个物品装入背包,使得在不超过背包最大容量 W 的前提下,装入背包的物品的总价值最大

注意:0-1 背包中的 “0-1” 指的是每个物品只能被选取一次(即要么选择该物品,要么不选,不存在把物品拆一半放入背包)。

这个0-1背包问题很经典。详情可以买本labuladong的算法笔记这本书看看,或者去网站看。

动态规划解法

背包问题无非就是状态 + 选择,状态转移方程比较特殊。

第一步:明确状态+选择
状态:只要给几个物品一个背包的容量限制,就形成了一个背包问题呀。所以状态有两个,就是背包的容量可选择的物品

选择:装进背包 or 不装进背包

框架:

for 状态1 in 状态1的所有取值:for 状态2 in 状态2的所有取值:for ...dp[状态1][状态2][...] = 择优(选择1,选择2...)

第二步:要明确 dp 数组的定义

  1. dp[i][w] 的定义

    • dp[i][w] 表示在考虑前 i 个物品时,当前背包容量为 w 的情况下可以获得的最大价值。
    • 注意:i 是从 1 开始计数的,意味着 i 对应的是第 i-1 个物品。
  2. 两种情况的状态转移

    • 如果不选第 i 个物品

      • 那么当前背包的最大价值等于不考虑第 i 个物品时的最大价值,即 dp[i][w] = dp[i-1][w]。这个值继承了前 i-1 个物品在背包容量为 w 时的最大价值。
    • 如果选第 i 个物品

      • 你可以将第 i 个物品装入背包,前提是当前背包的容量 w 要大于等于该物品的重量 wt[i-1]
      • 在这种情况下,当前物品的总价值应该等于第 i-1 个物品在容量为 w - wt[i-1] 时的最大价值,再加上该物品的价值 val[i-1]
      • 公式为:dp[i][w] = val[i-1] + dp[i-1][w - wt[i-1]]
// ①定义状态
int[][] dp[N+1][W+1]
// ②初始化状态 因为没有物品或者背包没有空间的时候,能装的最大价值就是 0
dp[0][..] = 0
dp[..][0] = 0
// ③状态转移方程
for i in [1..N]:for w in [1..W]:dp[i][w] = max(把物品 i 装进背包,不把物品 i 装进背包)
return dp[N][W]

代码

int knapsack(int W, int N, int[] wt, int[] val) {int N == wt.length;// 定义状态 dp[i][w] 表示: 对于前 i 个物品(从 1 开始计数),当前背包的容量为 w 时,这种情况下可以装下的最大价值是 dp[i][w]int[][] dp = new int[N + 1][W + 1];for (int i = 1; i <= N; i++) {for (int w = 1; w <= W; w++) {if (w - wt[i - 1] < 0) {// 这种情况下只能选择不装入背包dp[i][w] = dp[i - 1][w];} else {// 装入或者不装入背包,择优dp[i][w] = Math.max(dp[i - 1][w - wt[i-1]] + val[i-1], dp[i - 1][w]);}}}return dp[N][W];
}

题目:分割等和子集

原题链接: 分割等和子集
在这里插入图片描述

题解

方法1:

  • dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]:只要有一种情况成立,dp[i][j] 就为 true。即:
    • 要么不选第 i 个数(dp[i-1][j]true),则前 i-1 个数已经能够组成和为 j
    • 要么选择第 i 个数(dp[i-1][j-nums[i-1]]true),则前 i-1 个数能组成和为 j - nums[i-1],加上 nums[i-1] 就可以使总和为 j
 public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum += num;// 和为奇数时,不可能划分成两个和相等的集合if (sum % 2 != 0) return false;int target = sum / 2;// ①定义状态  dp[i][j] 表示前i个数中能否选出若干个  使得和为 j(j为背包容量)  则为true  否则falseboolean[][] dp = new boolean[nums.length + 1][target + 1];// ②初始化状态for (int i = 0; i <= nums.length; i++)dp[i][0] = true; // 背包容量为 0 时  不选任何物品就满足// ③状态转移for (int i = 1; i <= nums.length; i++) {for (int j = 1; j <= target; j++) {if (j - nums[i - 1] < 0) {// 背包容量不足,不能装入第 i 个物品dp[i][j] = dp[i - 1][j];} else {// 装入或不装入背包dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];}}}return dp[nums.length][target];}

这段代码是一个典型的0-1 背包问题的解法,问题是:能否从数组 nums 中找到若干个数,使它们的和等于 target(即总和的一半)。其中 dp[i][j] 表示前 i 个数能否选出若干个数,使它们的和恰好为 j。现在解释这一行代码:

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];

方法2:
在每次状态转移时,dp[i][j] 只依赖于上一行的状态 dp[i-1][j] 和 dp[i-1][j - nums[i-1]],所以可以将其优化为一维数组 dp[j],从而减少空间复杂度。

在遍历数组时,我们从后向前更新 dp 数组。这样做可以避免同一轮中重复使用同一个元素,即确保每个元素只能使用一次。

public boolean canPartition(int[] nums) {// 计算数组总和int sum = 0;for (int num : nums) {sum += num;}// 如果总和为奇数,无法分成两个子集if (sum % 2 != 0) return false;// 目标和是总和的一半int target = sum / 2;// ①定义状态  dp[i] 表示是否可以选出若干个元素,使得和为 iboolean[] dp = new boolean[target + 1];// ②初始化状态dp[0] = true;// ③状态转移for (int i = 0; i < nums.length; i++) {for (int j = target; j >= 0; j--) {if (j - nums[i] >= 0) {dp[j] = dp[j] | dp[j - nums[i]];}}}return dp[target];
}

❤觉得有用的可以留个关注~~~❤

这篇关于动态规划DP--背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139868

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表