当前位置:网站首页>Dynamic planning 111
Dynamic planning 111
2022-06-26 19:54:00 【Jiangjiangchun】
Basic questions
- knapsack problem ( Restricted fetch set , Seeking value or variety )
- raid homes and plunder houses
- Stock issues
- Subsequence problem
Basic solution
- dp Array , And the meaning of subscript
- The recursive formula
- dp Array initialization
- traversal order ( One dimensional array layer , Two-dimensional array two layers )
If you find the combination number, it's the outer layer for Loop through items , Inner layer for Traverse the backpack .
If you find the permutation number, it's the outer layer for Traverse the backpack , Inner layer for Loop through items .
if 01 knapsack , From the back to the front , Otherwise, from front to back
- Print array (debug)
Ideas :
The key is to think from the bottom up
First consider step ,
For example, the backpack problem , The steps are to put items one by one , How to put items is the optimal solution . There are two steps for each item , Don't put . Observe the overall situation and decide whether to put it or not .( Step back from your head to see if you want to put )
Another example is going up the steps , Step is step , Taking a few steps is the optimal solution , You can take one or two steps at a time . Observe the overall situation and decide whether to take one step or two .( Step back from your head , Is it one-step optimal or two-step optimal each time )
Every step-by-step problem , The next state has a problem that depends on the previous state. Consider using dynamic programming . Start with the last step , Imagine what operations are required for the state from the last step to the end
The value of dynamic programming array must be the answer
knapsack problem ( Seeking value )
It is a set of values with limits and values . The capacity of the backpack and the weight of the items constitute a limitation , The value of the goods is the value .
Two dimensional writing :
// 1 dp Array subscript and its meaning
// dp[i][j]
//i: from 0 -i Item No j: Backpack Capacity
//ij: from 0-i Take whatever you like , Put in j The greatest value in
// 2 The recursive formula
// dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+value)
// 3 dp Array initialization
// Physical truth
// 4 traversal order
// First pack your stuff
//
function bagProblem(weight,value,volume){
let count=weight.size+1
// 1 Definition dp
const dp=[]
// 3 initialization dp Array
for (let j = volume; j >= weight[0]; j--) {
dp[0][j] = dp[0][j - weight[0]] + value[0];
}
// 4 traversal order
for(let i=1;i<weight.length;i++){
for(let j=0;j<=volume;j++){
if(j<weight[i]){
dp[i][j]=dp[i-1][j]
}else{
// 2 The recursive formula
dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
}
Compress , One dimensional writing
From the picture above, we can get dp[i][j] Partly by dp[i-1][j] Copy it , Space can be omitted completely , Replace with a one-dimensional array
1、dp Definition
In one dimension dp Array ,dp[j] Express : Capacity of j The backpack , The value of the items carried can be up to dp[j].
2、 The recursive formula
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
here dp[j] There are two choices , One is to take yourself dp[j], One is to take dp[j - weight[i]] + value[i], Specify the maximum , After all, it's for maximum value ,
3、dp Array initialization
Initialize to 0
4、 traversal order
Cycle back and forth , Each acquisition state will not coincide with the previous acquisition state , So each item can only be taken once .
For two dimensions dp,dp[i][j] All through the upper layer, that is dp[i - 1][j] Come by calculation , On this floor dp[i][j] Not covered !
for(int i = 0; i < weight.size(); i++) { // Traverse the items
for(int j = bagWeight; j >= weight[i]; j--) { // Traverse the backpack capacity
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
// 1 dp Array subscript and its meaning
// dp[j]: Capacity of j The greatest value of time
//j: Capacity
// 2 The recursive formula
// dp[j]=max(dp[j],dp[j-w[i]]+value)
// there dp[j] In fact, it is a copy of the upper layer in a two-dimensional array , That is, the value of the previous item when it is not put
// 3 dp Array initialization
// All for 0
// 4 traversal order
// First pack your stuff
// Traverse the knapsack in reverse order , Prevent the upper state from being overwritten
function bagProblem(weight,value,volume){
let count=weight.size
// 1 Definition dp
const dp=[]
// 3 initialization dp Array
//
for(let i=0;i<volume;i++){
dp[i]=0
}
// 4 traversal order
for(let i=0;i<weight.length;i++){
// ps: Greater than weight, Less than weight You can't directly put it in and inherit the state of the previous level ( Not put directly )
for(let j=volume;j>=weight[i];j--){
// 2 Recursive formula
dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
}
}
}
Full backpack problem
Combination question
Topic link :https://leetcode-cn.com/problems/target-sum/
difficulty : secondary
Given an array of nonnegative integers ,a1, a2, ..., an, And a target number ,S. Now you have two symbols + and -. For any integer in the array , You can go from + or - Select a symbol to add to the front .
Return can make the final array and the target number S Of all methods to add symbols .
Limit :
left = (target + sum)/2 .
step
determine dp The meaning of arrays and subscripts
dp[j] Express : fill j( Include j) Such a large volume bag , Yes dp[i] Methods
In fact, you can also use two-dimensional dp Array to solve the problem ,dp[i][j]: Use Subscript to be [0, i] Of nums[i] Can fill up j( Include j) Such a large bag , Yes dp[i][j] Methods .
2、 The recursive formula
Don't consider nums[i] Under the circumstances , The filling capacity is j - nums[i] The backpack , Yes dp[j - nums[i]] Medium method .
So just get nums[i] Words , manage to put together dp[j] There is dp[j - nums[i]] Methods .
For example ,nums[i] = 2:dp[3], The capacity of the filled backpack is 3 Words , Yes dp[3] Methods .
Then you just need to get one 2(nums[i]), Yes dp[3] Method can aggregate a capacity of 3 The backpack , Correspondingly, there are many ways to gather the capacity of 5 The backpack .
So you need to take These methods add up ,dp[i] += dp[j - nums[j]
3、dp How to initialize an array
As can be seen from the recursive formula , At initialization time dp[0] Be sure to initialize to 1, because dp[0] Is the origin of all recursive results in the formula , If dp[0] yes 0 Words , The recursive result will be 0.
dp[0] = 1, It's also easy to explain in theory , The full capacity is 0 The backpack , Yes 1 Methods , It's just pretend 0 Item .
dp[j] The values corresponding to other subscripts should be initialized to 0, It can also be seen from the recursive formula ,dp[j] Make sure it's 0 The initial value of the , In order to correctly by dp[j - nums[i]] derived .
4、 traversal order
01 Knapsack problem dp The traversal ,nums Put it in the outer loop ,target Cycle, , And the internal circulation is reversed .
Recurrence formulas of several knapsacks
Ask if you can fill your backpack ( Or how much at most ):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); , The corresponding topics are as follows :
There are several ways to fill a backpack :dp[j] += dp[j - nums[i]] , The corresponding topics are as follows :
Ask if the back package is full of maximum value :dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); , The corresponding topics are as follows :
Ask the minimum number of all items in a full backpack :dp[j] = min(dp[j - coins[i]] + 1, dp[j]); , The corresponding topics are as follows :
raid homes and plunder houses
边栏推荐
- IK分词器
- 两个文件 合并为第三个文件 。
- 项目实战四:用户登录及token访问验证(reids+jwt)
- Development principle analysis and source code of dapp-lp single and dual currency liquidity pledge mining system
- What are the specific steps for opening a stock account? Is it safe to open an account online?
- ImageView, glide load long picture (glide load picture)
- Feign远程调用
- 动态规划111
- 回溯思路详解
- 知识点总结
猜你喜欢
随机推荐
知識點總結
动态规划111
Basic and necessary common plug-ins of vscade
抖音实战~搜索页面~视频详情
JS mobile terminal touch screen event
Nftgamefi chain game system development detailed solution - chain game system development principle analysis
C primer plus学习笔记 —— 3、字符的IO(输入/输出)
Feign remote call
Solidity - contract inheritance sub contract contains constructor errors and one contract calls the view function of another contract to charge gas fees
抖音实战~分享模块~短视频下载(保存到相册)
【Kubernetes】Kubernetes 原理剖析与实战应用(更新中)
Xlua get button registration click event of ugui
Micro service single sign on system (SSO)
证券开户安全吗,有没有什么危险呢
数据库范式和主码的选择
IK分词器
MySQL - subquery usage
[kubernetes] kubernetes principle analysis and practical application (under update)
On the escape of inequality value
Some cold knowledge about QT database development