当前位置:网站首页>Classical dynamic programming: complete knapsack problem
Classical dynamic programming: complete knapsack problem
2020-11-06 01:18:03 【itread01】
Finish reading this article , You can go and get the following questions : [518. Change II](https://leetcode-cn.com/problems/coin-change-2) **-----------** Change 2 It's a variant of another typical knapsack problem , As we have said earlier [ Classical dynamic programming :0-1 Knapsack problem ](https://labuladong.gitbook.io/algo). ** I hope you've read the first two articles **, I've seen the dynamic programming and knapsack problem , This article continues with the knapsack problem , List a variant of the knapsack problem . This article talks about LeetCode The first 518 Title Coin Change 2, The title is as follows :  ```java int change(int amount, int[] coins); ``` PS: To Coin Change 1, Before we did [ Detailed explanation of dynamic programming routine ](https://labuladong.gitbook.io/algo) Yes . ** We can turn this problem into a knapsack problem **: There's a backpack , The maximum capacity is `amount`, There's a range of things `coins`, The weight of each item is `coins[i]`,** The number of each item is unlimited **. How many ways are there , It can fill the backpack exactly ? This problem and the two knapsack problems we talked about earlier , One of the biggest differences is , The number of each item is infinite , This is also the legend of 「** Complete knapsack problem **」, Nothing big , It's just a little change in the state transfer equation . The following is a description of the knapsack problem , Continue to analyze according to the process . PS:** I've seriously written about 100 Many original articles , Hand brush 200 Daoli is the subject , All published in [labuladong It's a copy of the algorithm ](https://links.jianshu.com/go?to=https%3A%2F%2Flabuladong.gitbook.io%2Falgo%2F), Continuous update **. Suggest collecting ,** Write the title in the order of my article **, After mastering all kinds of algorithms, it will be like a fish in water to throw it into the sea of questions . ### Thinking of problem solving ** The first step is to be clear about two things ,「 Status 」 and 「 Choice 」**. There are two states , Namely 「 The capacity of the backpack 」 and 「 Optional items 」, The choice is 「 Put it in a backpack 」 perhaps 「 Not in a backpack 」 Well , The knapsack problem is like this . Understand the state and the choice , The dynamic programming problem is basically solved , Just put this frame around and it's done : ```python for Status 1 in Status 1 All values of : for Status 2 in Status 2 All values of : for ... dp[ Status 1][ Status 2][...] = Calculation ( Choice 1, Choice 2...) ``` ** The second step is to be clear about `dp` The definition of arrays **. First of all, take a look at what you just found 「 Status 」, There are two , In other words, we need a two-dimensional `dp` Array . `dp[i][j]` The definition of is as follows : If only before use `i` Items , When the backpack capacity is `j` When , Yes `dp[i][j]` There are ways to fill a backpack . In other words , Translation back to our title means : ** If only `coins` In front of `i` The face value of a coin , If you want to make up the amount `j`, Yes `dp[i][j]` Planting method **. After the above definition , You can get : base case For `dp[0][..] = 0, dp[..][0] = 1`. Because if you don't use any denomination , You can't come up with any amount ; If the target amount is 0, So “ Governing by inaction ” It's the only way to make it up . The answer we want to get is `dp[N][amount]`, among `N` For `coins` The size of the array . The general idea of PN code is as follows : ```python int dp[N+1][amount+1] dp[0][..] = 0 dp[..][0] = 1 for i in [1..N]: for j in [1..amount]: Put the goods i Put it in a backpack , Don't put things i Put it in a backpack return dp[N][amount] ``` ** The third step , According to 「 Choice 」, Thinking about the logic of state transition **. Be careful , The special point of our problem is that the number of items is infinite , So this is different from the previous article on backpacking . ** If you don't put this `i` Put an item in a backpack **, That means you don't use `coins[i]` This coin in denomination , So make up the denomination `j` Method number of `dp[i][j]` Should be equal to `dp[i-1][j]`, Inherit the result before . ** If you put this first `i` Items are packed into a backpack **, That means you use `coins[i]` This coin in denomination , So `dp[i][j]` Should be equal to `dp[i][j-coins[i-1]]`. First of all, because `i` It's from 1 Starting , therefore `coins` The index of is `i-1` The second is the third `i` The face value of a coin . `dp[i][j-coins[i-1]]` It's not hard to understand , If you decide to use this denomination , Then we should pay attention to how to make up the amount `j - coins[i-1]`. For example , You want to use the face value of 2 To make up the sum of 5, So if you know, make up the amount 3 Methods , Plus a denomination of 2 The coin of , No, we can come up with 5 Yes . ** To sum up, there are two choices , And what we want is `dp[i][j]` yes 「 How many tricks are there 」, therefore `dp[i][j]` The value of should be the sum of the above two choices **: ```java for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) { if (j - coins[i-1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j-coins[i-1]]; return dp[N][W] ``` ** The last step , Translate pseudo code into code , Deal with some boundary conditions **. I use Java Written code , Translate all the above ideas , And dealt with some boundary problems : ```java int change(int amount, int[] coins) { int n = coins.length; int[][] dp = amount int[n + 1][amount + 1]; // base case for (int i = 0; i <= n; i++) dp[i][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) if (j - coins[i-1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]]; else dp[i][j] = dp[i - 1][j]; } return dp[n][amount]; } ``` and , We can find through observation that ,`dp` The transfer of an array is only as good as `dp[i][..]` and `dp[i-1][..]` About , So you can compress the State , Further reduce the space complexity of the algorithm : ```java int change(int amount, int[] coins) { int n = coins.length; int[] dp = new int[amount + 1]; dp[0] = 1; // base case for (int i = 0; i < n; i++) for (int j = 1; j <= amount; j++) if (j - coins[i] >= 0) dp[j] = dp[j] + dp[j-coins[i]]; return dp[amount]; } ``` This solution is exactly the same as before , Two dimensional `dp` The array is compressed into one dimension , Time complexity O(N\*amount), Space complexity O(amount). thus , This change exchange problem is also solved through the framework of knapsack problem . **_____________** my [ Online e-books ](https://labuladong.gitbook.io/algo) Yes 100 An original article , Hands with brushes 200 Daoli is the subject , Suggest collecting ! Corresponding GitHub [ Algorithms warehouse ](https://github.com/labuladong/fucking-algorithm) You've got 70k star, Welcome
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World