DP backpack summary

There were a lot of things in the last two weeks , Elective courses , All the required courses have examinations , Make the whole person very unhappy , Of course, I can spend a hard week in the computer room next week , At least you don't have to sweat to learn , Well, back to business , What I read this time are all other people's blogs , The title above Luogu , Seriously, I don't know how to distinguish the knapsack problem in dynamic programming , For me, learning backpack is better than looking directly at the analysis given by others' understanding of the topic .

CF Bottles 0-1 knapsack _cyl The blog of Xianyun Qiaoqiao -CSDN Blog

My understanding of the solution to this problem is ： Find the minimum number of bottles needed according to the capacity of each bottle , And then based on i A bottle contains j What is the maximum amount of water you can get in a bottle . Keep up with the previous situation , Of course, you need to sort before enumerating , Sort by capacity . Finally, we can get the answer . When I first saw the meaning of the title, I thought of something , Can we use greed to solve this problem , Isn't it the least , Just be greedy , But the problem is to find the minimum on the basis of the minimum , therefore , Greed is not easy to achieve .

[NOIP2006 Improvement group ] Jin Ming's budget - Luogu

This topic is rather vague at the beginning , I just don't know what kind of backpack is suitable , But after reading other people's solutions, I found that it was a common knapsack problem , It just takes several times . Generally, there are only... Attachments at most 2 individual , So preprocess the attachment of each main component first ... son[i,1] Express i The first attachment of son[i,2] Express i The second attachment of is divided into 5 class dp Main parts ：1. Don't choose this main piece .2. Select only this main component .3. Select the main component and the first accessory .4. Select the main component and the second accessory .5. Select the main component plus the first attachment and the second attachment . Once each dp You can solve the problem .

ZOJ 3769 （ Pack in groups ）_cyl The blog of Xianyun Qiaoqiao -CSDN Blog

This is the one that makes me confused , I haven't figured it out yet ,01 How to distinguish backpacks and group backpacks in terms of topics , Let's just talk about this topic , The first thing I saw was that I was trying to do something from one foundation to the other dp Do you , But after reading the solution, I found that it was not like that . The explanation given by the author is ： Each kind of equipment can only be equipped with one piece , It's kind of like 0-1 knapsack .0-1 The capacity of the backpack should be m（ toughness ）, But what this problem requires is that it must be greater than or equal to m The resilience of , Unlike 0-1 The capacity in the backpack can be split at will . Then I understand it as carrying out another on one basis dp, As long as it can be split 01, Not splitting is grouping .

HDU 2955 （01 The backpack is out of shape ）_cyl The blog of Xianyun Qiaoqiao -CSDN Blog

This 01 The deformation problem of backpack at first glance , I thought I had to be greedy , I just put less than p The probabilities add up , It turns out that it's not ,dp[i] It means the money from the robbery i Next , You are most likely not to be caught .dp[0] The probability of being caught without robbery is 1, Then follow 0-1 Just write the backpack .

yPOJ 1149 （0-1 The backpack is out of shape ）_cyl The blog of Xianyun Qiaoqiao -CSDN Blog

Another 0-1 The deformation problem of backpack , Of course, when I got the title, I knew it was 01, Because every kind of commodity has to be bought , This is a 0-1 knapsack problem . And then on this basis dp 了 . The question is how to count each combination . The solution is to treat each combination as a commodity , We record the number of products in each combination , If we choose this product , The number of corresponding items will be subtracted and compared .

summary ： My understanding of backpacks is still in the clouds , An ordinary backpack simply uses the most basic dynamic transfer equation ,01 Backpack means choosing to take or not to take when the capacity is determined , To find the best interests , Of course, you can also choose to take , To determine the minimum cost . That is to say, this is carried out on a certain basis dp, And each point and type can choose to or not , Then look for the best interests . Like multiple backpacks , Group backpacks or something , The code so far , I didn't fully understand . The last blog of this semester , I wanted to write a little more , A little more , But it's really more than the heart and less than the power , I can only blame myself for not doing enough .