动态规划-01背包问题

这篇具有很好参考价值的文章主要介绍了动态规划-01背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、题目描述(截图来的)

动态规划-01背包问题,动态规划,算法

动态规划-01背包问题,动态规划,算法

2、题目解析 + 算法原理(第一问)

算法思路: 背包问题的状态表⽰⾮常经典,如果⼤家不知道怎么来的,就把它当成⼀个「模板」记住吧~ 我们先解决第⼀问:

1. 状态表⽰: dp[i][j] 表⽰:从前 i 个物品中挑选,总体积「不超过」 j ,所有的选法中,能挑选出来 的最⼤价值。

2. 状态转移⽅程: 线性 dp 状态转移⽅程分析⽅式,⼀般都是根据「最后⼀步」的状况,来分情况讨论: i. 不选第 i 个物品:相当于就是去前 i - 1 个物品中挑选,并且总体积不超过 j 。此 时 dp[i][j] = dp[i - 1][j] ; ii. 选择第 i 个物品:那么我就只能去前 i - 1 个物品中,挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是这种状态不⼀ 定存在,因此需要特判⼀下。 综上,状态转移⽅程为: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

3、初始化

我们多加⼀⾏,⽅便我们的初始化,此时仅需将第⼀⾏初始化为 0 即可。因为什么也不选,也能 满⾜体积不⼩于 j 的情况,此时的价值为 0 。

4.填表顺序

根据「状态转移⽅程」,我们仅需「从上往下」填表。

5.dp的返回值

返回 dp[n][V]

3、算法思路 + 解析(第二问)

        第⼆问仅需微调⼀下 dp 过程的五步即可。 因为有可能凑不⻬ j 体积的物品,因此我们把不合法的状态设置为 -1 。

1. 状态表⽰: dp[i][j] 表⽰:从前 i 个物品中挑选,总体积「正好」等于 j ,所有的选法中,能挑选出 来的最⼤价值。

2. 状态转移⽅程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。 但是在使⽤ dp[i - 1][j - v[i]] 的时候,不仅要判断 j >= v[i] ,⼜要判断 dp[i - 1][j - v[i]] 表⽰的情况是否存在,也就是 dp[i - 1][j - v[i]] != -1

3. 初始化: 我们多加⼀⾏,⽅便我们的初始化: i. 第⼀个格⼦为 0 ,因为正好能凑⻬体积为 0 的背包; ii. 但是第⼀⾏后⾯的格⼦都是 -1 ,因为没有物品,⽆法满⾜体积⼤于 0 的情况。

4. 填表顺序: 根据「状态转移⽅程」,我们仅需「从上往下」填表即可。

5. 返回值: 由于最后可能凑不成体积为 V 的情况,因此返回之前需要「特判」⼀下。

//第一种方案

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main()
{
 // 读⼊数据
 cin >> n >> V;
 for(int i = 1; i <= n; i++)
 cin >> v[i] >> w[i];
 // 解决第⼀问
 for(int i = 1; i <= n; i++)
 for(int j = 0; j <= V; j++) // 修改遍历顺序
 {
 dp[i][j] = dp[i - 1][j];
 if(j >= v[i])
 dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
 }
 
 cout << dp[n][V] << endl;
 // 解决第⼆问
 memset(dp, 0, sizeof dp);
 for(int j = 1; j <= V; j++) dp[0][j] = -1;
 for(int i = 1; i <= n; i++)
 for(int j = 0; j <= V; j++) // 修改遍历顺序
 {
 dp[i][j] = dp[i - 1][j];
 if(j >= v[i] && dp[i - 1][j - v[i]] != -1)
 dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
 }
 
 cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
 return 0;
}

4.背包问题的空间优化

空间优化: 背包问题基本上都是利⽤「滚动数组」来做空间上的优化:

        i. 利⽤「滚动数组」优化;

        ii. 直接在「原始代码」上修改。

在01背包问题中,优化的结果为:

        i. 删掉所有的横坐标;

        ii.修改一下j的遍历顺序文章来源地址https://www.toymoban.com/news/detail-848181.html

        
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main()
{
 // 读⼊数据
 cin >> n >> V;
 for(int i = 1; i <= n; i++)
 cin >> v[i] >> w[i];
 // 解决第⼀问
 for(int i = 1; i <= n; i++)
 for(int j = V; j >= v[i]; j--) // 修改遍历顺序
 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
 cout << dp[V] << endl;
 // 解决第⼆问
 memset(dp, 0, sizeof dp);
 for(int j = 1; j <= V; j++) dp[j] = -1;
 for(int i = 1; i <= n; i++)
 for(int j = V; j >= v[i]; j--)
 if(dp[j - v[i]] != -1) 
 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
 
 cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
 return 0;
}

到了这里,关于动态规划-01背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法套路十四——动态规划之背包问题:01背包、完全背包及各种变形

    如果对递归、记忆化搜索及动态规划的概念与关系不太理解,可以前往阅读算法套路十三——动态规划DP入门 背包DP介绍:https://oi-wiki.org/dp/knapsack/ 0-1背包:有n个物品,第i个物品的体积为w[i],价值为v[i],每个物品至多选一个, 求体积和不超过capacity时的最大价值和,其中i从

    2024年02月10日
    浏览(55)
  • C++算法初级11——01背包问题(动态规划2)

    辰辰采药 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时

    2024年02月02日
    浏览(47)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(51)
  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(46)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(54)
  • 力扣算法刷题Day42|动态规划:01背包问题 分割等和子集

    力扣题目:01背包问题(二维数组) 刷题时长:参考题解 解题方法:动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路:两层for循环,第一层i遍历物品,第二层j枚举背包容量以内所有值 确定dp数组及下标的含义:dp[i][j] 表示从下标

    2024年02月13日
    浏览(59)
  • 算法竞赛必考算法——动态规划(01背包和完全背包)

    1.1题目介绍 1.2思路一介绍(二维数组) 代码如下: 1.3思路二介绍(一维数组) 空间优化   为什么可以使用一维数组?   我们先来看一看01背包问题的状态转移方程,我们可以发现 f[i]只用到了f[i-1],其他的是没有用到的,我们可以用滚动数组来做。   还有一个原因就是我

    2024年02月02日
    浏览(41)
  • 【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型

    目录 背包问题概述 01 背包问题 01背包⭐⭐  【算法原理】 第一问 第二问 C++ 算法代码 复杂度分析 【空间优化 - 滚动数组】 C++ 算法代码 复杂度分析 分割等和子集⭐⭐ 【算法原理】  对于类01背包问题 C++ 算法代码  【空间优化 - 滚动数组】  C++ 算法代码 目标和⭐⭐ 【算

    2024年02月05日
    浏览(54)
  • 算法学习笔记(动态规划——01背包)

    先来聊聊动态规划,动态规划是分治法的一种体现,把一个问题分解成若干个子集,通过当前状态,经过操作得到下一个状态,最后得到最优问题解的一种方法。 步骤: 设定状态,保存状态 根据状态设定转移方程 确定边界 其中的01背包解决的是关于选择的动态规划问题,

    2024年03月25日
    浏览(50)
  • 动态规划(01背包问题)

    本文默认读者具有动态规划前置知识 动态规划的特点: 重叠子问题 状态转移方程 最优子结构 题型: 求最值 解题套路: 明确【状态】 明确【选择】 明确dp函数/数据的定义 明确base case 例:给你一个可装载容量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第

    2024年04月16日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包