当前位置:网站首页>0-1 knapsack problem (I)
0-1 knapsack problem (I)
2022-07-06 15:39:00 【Xiaogeng who loves learning】
List of articles
0-1 knapsack problem ( One )
Tips : After writing the article , Directories can be generated automatically , How to generate it, please refer to the help document on the right
List of articles
Preface
Tips : The following is the main body of this article , The following cases can be used for reference
One 、0-1 What is the knapsack problem ?
The knapsack problem is 「 Dynamic programming 」 It's a very classic class of problems , Knapsack problem essentially belongs to combinatorial optimization 「NP Problem completely 」. Because there are too many combinations , Therefore, the problem cannot be solved by exhaustive method , That's why 「 knapsack problem 」 Will use 「 Dynamic programming 」 To find out the root cause . Here is a simple example 0-1 knapsack problem .
Two 、 To divide into equal and subsets (Leetcode 416 secondary )
1. Problem description
To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .
2. Description of algorithm
2.1 0-1 The basic idea of knapsack problem
0-1 Knapsack problem is essentially a dynamic programming problem , The essence of dynamic programming is to find the numerical change caused by the change of the next state and the previous state , The state transition equation ,dp[i][j] and dp[i-1][j] The relationship between .
0-1 The knapsack problem is actually the same problem ,dp[i][j]=max(dp[i-1][j],dp[i-1][jv[i]]+wight[i]), It means to traverse one item at a time , There are two options : Take it or not , The volume of the backpack will be reduced , If you don't take it, you will keep the original state .
2.2 Analysis of specific problems
This problem can be converted to knapsack problem , Problem modeling process : How big is the volume of the backpack 、 The quantity and value of items 、 The form of the result
1. Number of items :nums Of size
2. The value of the goods :nums The corresponding value
3. The volume of the backpack : This is the difficulty of the general knapsack problem , The question here does not specify the maximum value of the backpack , At this time, we need to deform the problem : Make the sum of the elements of the two subsets equal ==》 Sum of each subset == All elements and 1/2, Therefore, the volume of the backpack is also obvious, that is, the sum of all elements 1/2.
4. The form of the result : First of all, we have to analyze what the result of our calculation is , The calculated value is the maximum value that can be obtained by taking this as the backpack volume , The question is whether they can be equal , Therefore, the form of the result can be transformed into : Whether the backpack can be filled , That is, whether the maximum value is equal to the volume of the backpack .
This article only introduces the most primitive solution of knapsack problem , This is also the original form , The following articles will focus on the problem to make a variety of variants and optimization
2.4 Code display :
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));
// First processing 「 Consider the first item 」 The situation of
for (int i = 0; i <= C; i++) {
dp[0][i] = i>=nums[0] ? nums[0] : 0;
}
// To deal with 「 Consider the rest 」 The situation of
for (int i = 1; i < N; i++) {
for (int j = 0; j < C + 1; j++) {
// Don't select this item
int n = dp[i - 1][j];
// Select the item , Premise 「 Residual capacity 」 Greater than or equal to 「 Volume of goods 」
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;
}
};
summary
Tips : Here is a summary of the article :
Today I mainly explained 「 What is the knapsack problem 」、「 What is the essence of the knapsack problem 」 as well as 「 Why the knapsack problem needs to be solved by dynamic programming, and the knapsack problem solving routines and deformation problems are difficult , among 「01 knapsack 」 The problem is at the heart of many knapsack problems .
边栏推荐
- LeetCode#198. raid homes and plunder houses
- Es6--- two methods of capturing promise status as failed
- Learning record: use stm32f1 watchdog
- ucorelab3
- Contest3145 - the 37th game of 2021 freshman individual training match_ A: Prizes
- 力扣刷题记录--完全背包问题(一)
- Mysql database (IV) transactions and functions
- Cost accounting [20]
- STM32学习记录:LED灯闪烁(寄存器版)
- Research Report on medical toilet industry - market status analysis and development prospect forecast
猜你喜欢
ucorelab4
Learning records: serial communication and solutions to errors encountered
TCP的三次握手与四次挥手
Mysql database (IV) transactions and functions
Learning record: understand systick system timer and write delay function
12306: mom, don't worry about me getting the ticket any more (1)
Matlab example: two expressions of step function
学习记录:串口通信和遇到的错误解决方法
The wechat red envelope cover designed by the object is free! 16888
Threads and thread pools
随机推荐
ucorelab4
csapp shell lab
ucore lab5
How to change XML attribute - how to change XML attribute
C4D quick start tutorial - creating models
Cost accounting [23]
JS --- all basic knowledge of JS (I)
Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
STM32学习记录:输入捕获应用
Medical colposcope Industry Research Report - market status analysis and development prospect forecast
Contest3145 - the 37th game of 2021 freshman individual training match_ A: Prizes
MATLAB综合练习:信号与系统中的应用
ArrayList set
JS --- all knowledge of JS objects and built-in objects (III)
Crawling cat's eye movie review, data visualization analysis source code operation instructions
学习记录:使用STM32F1看门狗
Accounting regulations and professional ethics [3]
ucore lab 2
力扣刷题记录--完全背包问题(一)
How to become a good software tester? A secret that most people don't know