当前位置:网站首页>0-1背包问题(一)
0-1背包问题(一)
2022-07-06 09:25:00 【爱学习的小耿】
系列文章目录
0-1背包问题(一)
提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
前言
提示:以下是本篇文章正文内容,下面案例可供参考
一、0-1背包问题是什么?
背包问题是「动态规划」中十分经典的一类问题,背包问题本质上属于组合优化的「NP 完全问题」。因为组合数量过多,因此无法通过穷举法来解决问题,这就是为什么「背包问题」会使用「动态规划」来求解的根本原因。下面通过简单示例来讲述0-1背包问题。
二、分割等和子集(Leetcode 416中等)
1.问题描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
2.算法概述
2.1 0-1背包问题问题的基本思路
0-1背包问题本质上还是动态规划问题,动态规划的问题的本质在于寻找下一个状态和上个状态的变化带来的数值变化,即状态转移方程,dp[i][j]和dp[i-1][j]之间的关系。
0-1背包问题其实也是同样的问题,dp[i][j]=max(dp[i-1][j],dp[i-1][jv[i]]+wight[i]),意思就是每次遍历到一个物品,都有两个选择:取或者不取,取了背包的容积就会减少,不取则保持原来的状态。
2.2 具体问题分析
此题可以转换为背包问题,问题建模过程:背包的容积有多大、物品的数量和价值、结果形式
1.物品的数量:nums的size
2.物品的价值:nums对应的数值
3.背包的容积:这个是一般形如背包问题的难点,此处题中并没有明说背包最大值是多少,此时需要把问题变形:使两个子集的元素和相等==》每个子集的和==所有元素和的1/2,因此背包的容积也显而易见即所有元素和的1/2。
4.结果形式:首先得分析我们计算出来的结果是什么,计算获得的值为以此为背包容积所能获得的最大值,问题是能否相等,因此结果的形式就可以转换为:背包能否被装满,即最大值是否等于背包的容积。
本文只介绍最原始的背包问题解法,这也是最初的形式,后面几篇都会围绕该题做出多种变种和优化
2.4 代码展示:
class Solution {
public:
bool canPartition(vector<int>& nums) {
int N=nums.size();
int sum=0;
for(int i=0;i<N;i++)
{
sum+=nums[i];
}
if(sum%2!=0) return false;
int C=sum/2;
vector<vector<int>>dp(N,vector<int>(C+1,0));
// 先处理「考虑第一件物品」的情况
for (int i = 0; i <= C; i++) {
dp[0][i] = i>=nums[0] ? nums[0] : 0;
}
// 再处理「考虑其余物品」的情况
for (int i = 1; i < N; i++) {
for (int j = 0; j < C + 1; j++) {
// 不选该物品
int n = dp[i - 1][j];
// 选择该物品,前提「剩余容量」大于等于「物品体积」
int y =j>nums[i]? dp[i - 1][j-nums[i]]+nums[i]:0;
dp[i][j] =max(n,y);
}
}
return dp[N-1][C]==C;
}
};
总结
提示:这里对文章进行总结:
今天主要讲解了「什么是背包问题」、「背包问题的本质是什么」以及「为什么背包问题需要用到动态规划来求解以及背包的解决套路和变形题的难点,其中「01背包」问题是众多背包问题中核心。
边栏推荐
- The wechat red envelope cover designed by the object is free! 16888
- Crawler series of learning while tapping (3): URL de duplication strategy and Implementation
- ucore lab 6
- What are the software testing methods? Show you something different
- Contest3145 - the 37th game of 2021 freshman individual training match_ A: Prizes
- LeetCode#53. Maximum subarray sum
- Lab 8 file system
- Medical colposcope Industry Research Report - market status analysis and development prospect forecast
- JS --- detailed explanation of JS facing objects (VI)
- Learning record: STM32F103 clock system overview working principle
猜你喜欢
Learning record: how to perform PWM output
Introduction to safety testing
Learning record: Tim - capacitive key detection
[pytorch] simple use of interpolate
ucorelab3
Learning records: serial communication and solutions to errors encountered
FSM and I2C experiment report
LeetCode#62. Different paths
软件测试有哪些常用的SQL语句?
ucore lab 2
随机推荐
What to do when programmers don't modify bugs? I teach you
STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
软件测试Bug报告怎么写?
Introduction to safety testing
JDBC介绍
Research Report on market supply and demand and strategy of China's medical chair industry
China's PCB connector market trend report, technological innovation and market forecast
JS --- all basic knowledge of JS (I)
Medical colposcope Industry Research Report - market status analysis and development prospect forecast
ucore lab7
Lab 8 文件系统
Programmers, how to avoid invalid meetings?
Learning record: understand systick system timer and write delay function
Mysql database (I)
Preface to the foundations of Hilbert geometry
Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
Interface test interview questions and reference answers, easy to grasp the interviewer
STM32學習記錄:輸入捕獲應用
[pytorch] simple use of interpolate
How to write the bug report of software test?