代碼隨想錄算法訓練營|第四十四天|01背包问题 二维、01背包问题 一维、416. 分割等和子集。刷题心得（c++）

2023-10-21 03:04
文章标签 算法 c++ 问题 分割 第四十四 01 416 子集 背包 刷题 心得 二维 一维 代碼 隨想錄 訓練營

本文主要是介绍代碼隨想錄算法訓練營|第四十四天|01背包问题 二维、01背包问题 一维、416. 分割等和子集。刷题心得（c++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

01背包問題 - DP二維數組

01 背包問題描述

暴力解

動態規劃

確認DP數組以及下標的含意

確定遞推公式

01背包问题 一维

一维DP 数組(滾動数組)

動態規劃五部曲

定義DP数組以及其下標含意

遞推公式

初始化

遍歷順序

讀題

416. 分割等和子集

自己看到题目的第一想法

看完代码随想录之后的想法

416. 分割等和子集- 實作

思路

Code

總結

自己实现过程中遇到哪些困难

今日收获，记录一下自己的学习时长

相關資料

01背包問題 - DP二維數組

01 背包問題描述

背包最高可承重重量為j，有i件物品，每件物品的重量為weight[i]，並且對應的價值為value[i]，每件物品只能用一次

背包放入那些物品可以達到最高的價值

01 的含意，就是每件物品只能用一次，取(1)或不取(0)

暴力解

01背包問題可以使用暴力解來解出來，就是去窮舉每一個東西取或不取最後找出最大的價值和

可以使用回溯算法去做，但時間複雜度會是 $O(2^n)$

動態規劃

確認DP數組以及下標的含意

dp[i][j]: [0, i]物品任意取，可放進容量為j的背包的最大價值。

確定遞推公式

在描述中物品有兩種狀態，一個是不放入背包，一個是放入背包

  1. 物品i 不放入背包: 代表我們要知道的是當下的i不放入背包j的最大價值是多少，那就是dp[i - 1][j]，背包容量為j，在不放入i之前最大的是i - 1，所以得出dp[i - 1][j]
  2. 物品i放入背包: 代表我們要知道當下物品i放入背包之後，剩餘的背包重量可得到最大的價值是多少: dp[i - 1][j - weight[i]]，這代表的是，背包可承重的重量為j 減去目前i的重量weight[i]並且不包含當前i的重量，最後再加入value[i] 代表當前的價值加上扣除當前重量的背包所能得到的最大價值。最後整合為dp[i - 1][j - weight[i]] + value[i]

那我們是要取最大的數值，所以遞推公式會變成 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i] + value[i]);

01背包问题 一维

一维DP 数組(滾動数組)

藉由壓縮dp[i - 1] 到dp[i] 因為在二維的DP遞推方程裡是dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - weight[i] + value[i])

假設壓縮成一维數組，可以看成假設dp[j]跟dp[j - weight[i]] + value[i] 不用將上一層拷貝而是透過不斷更新dp[j] 來比較值。

其狀態就像是滾動著更新我們的dp数組值，透過維護dp[j]的遍歷順序來維護裡面的值與dp二維数組一致

動態規劃五部曲

定義DP数組以及其下標含意

dp[j]: 背包重量為j的最大價值為dp[j]

遞推公式

與二维數組一樣，dp[j]的數值可以透過當前dpj 以及dp[j - weighti 兩者做比較。

所以遞推公式可以將i去除掉變成

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

初始化

dp数組在dp[0]時，根據定義，需要將dp[0]初始化為0，並且根據遞推公式，每次都會取最大值，所以其他数值也應該初始化為dp数組中最小的值，也就是0

所以在初始化時，將dp数組全部初始化為0

遍歷順序

在二维數組中，每一層的數值都是當前位置的正上方以及左上方的數據得出

從二维壓縮成一维數組，我們需要模擬二维數組的方式

所以根據我們的遞推公式，我們不能使用正序遍歷，不然原本在二维數組中左上方的數據就會被覆蓋掉

而使用倒序可以保證每一層的數據都是由二维數組上一層正上方以及左上方得出的。

透過倒敘更新，確保了在考慮當前物品時，dp[j - weight[i]]仍然代表前一個物品的狀態，但是如果使用正序，那dp[j - weight[i]]就會被提早更新了

如下

假設我們有以下物品和背包：

物品重量: w = [2,3] 物品價值: v = [3,4] 背包最大容量: W = 5

  1. 使用一維數組正序更新時：

    物品\\背包 | 0 | 1 | 2 | 3 | 4 | 5 |    進行的操作
-----------------------------------    ------------   | 0 | 0 | 0 | 0 | 0 | 0 |    初始化2   | 0 | 0 | 3 | 3 | 3 | 3 |    考慮物品1 (w=2, v=3)3   | 0 | 0 | 3 | 4 | 7 | 7 |    考慮物品2 (w=3, v=4)

    當我們考慮物品2時，對於背包容量4，dp[4]是基於dp[1]（已被更新的）和dp[4-w[2]=1]計算

  2. 使用一維數組倒序更新時

    物品\\背包 | 0 | 1 | 2 | 3 | 4 | 5 |    進行的操作
-----------------------------------    ------------   | 0 | 0 | 0 | 0 | 0 | 0 |    初始化2   | 0 | 0 | 3 | 3 | 3 | 3 |    考慮物品1 (w=2, v=3)3   | 0 | 0 | 3 | 4 | 5 | 7 |    考慮物品2 (w=3, v=4)

    當我們考慮物品2和背包容量4時，dp[4]是基於dp[1]（尚未更新的）和dp[4-w[2]=1]計算的

在影片講解的部分，有個彈幕寫了以下這段，分享給你

一维数组就像走楼梯，你去二楼，就必须从一楼上，去三楼也要从一楼走；倒叙就还好比下楼，想去几楼都不用重复路过其他楼层。

並且需要先遍歷物品在遍歷背包，因為需要上一個物品的值，如果先遍歷背包，則只抓到一個物品的值。

讀題

416. 分割等和子集

自己看到题目的第一想法

看完跟01背包問題沒有辦法有很直接的連結，我大致有想到一個是dp[i][j]代表的是[0 ~ i][j ~ size()]的區間是否相等，但感覺有些地方沒有想清楚，先看題解。

看完代码随想录之后的想法

想法很巧妙如果有一個背包等於所有和的一半，剩下的元素相加也等於剩餘的一半 dp[j]: 容量為j的背包，最大價值為dp[j]，並且數組中的重量跟價值可以看成是一致的

並判斷dp[target] == target。dp数組初始化為0 ，並且背包重量設為target + 1

忘記思考到target如果不能被2整除，那就是要return false。

416. 分割等和子集- 實作

思路

  1. 定義DP數組以及下標的含意

    target: 假設子序和的重量為總和的一半，那代表另一半為剩餘的一半。

    假設總和除2餘1代表不會有一個子序和等於另一個子序和

    dp[j] : 背包重量 j 的最大價值為dp[j]

    nums数組中，重量與價值就是nums[i]

  2. 遞推公式

    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  3. 根據遞推公式，確定DP數組如何初始化

    dp[0]要初始化為0，其他部分也要更新為正整數下的最小位数0

  4. 確定遍歷順序

    避免覆蓋掉上一次的值，所以要使用倒敘遍歷

  5. 打印dp數組 (debug);

Code

class Solution {
public:bool canPartition(vector<int>& nums) {int target = 0;for(int i = 0; i < nums.size(); i++) {target += nums[i];}if (target % 2 == 1) return false;target /= 2;vector<int> dp(target + 1, 0);for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}if(dp[target] == target) return true;}return false;}
};

 

總結

自己实现过程中遇到哪些困难

困難點主要是在思考二维數組壓縮成一维數組的部分，這個部分思考比較久，並且在416分割等和子集中，也是遇到了點問題，在思考上沒有想到nums[i]是重量與價值相等，彈點通之後就比較理解了

今日收获，记录一下自己的学习时长

今天大概學了3hr，主要是在理解01背包的思維與想法。

相關資料

● 今日学习的文章链接和视频链接

算法圖解

01背包问题 二维

https://programmercarl.com/背包理论基础01背包-1.html

视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

01背包问题 一维

https://programmercarl.com/背包理论基础01背包-2.html

视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

416. 分割等和子集

本题是 01背包的应用类题目

https://programmercarl.com/0416.分割等和子集.html

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili

这篇关于代碼隨想錄算法訓練營|第四十四天|01背包问题 二维、01背包问题 一维、416. 分割等和子集。刷题心得（c++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/251497。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
poj2576(二维背包)

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（二维背包）

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(背包的变形题)

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2