当前位置：网站首页>Classical dynamic programming: complete knapsack problem
Classical dynamic programming: complete knapsack problem
20201106 01:18:03 【itread01】
Finish reading this article , You can go and get the following questions ： [518. Change II](https://leetcodecn.com/problems/coinchange2) **** Change 2 It's a variant of another typical knapsack problem , As we have said earlier [ Classical dynamic programming ：01 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 ： ![title](https://gitee.com/labuladong/pictures/raw/master/knapsackCoin/title.jpg) ```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 twodimensional `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[i1][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][jcoins[i1]]`. First of all, because `i` It's from 1 Starting , therefore `coins` The index of is `i1` The second is the third `i` The face value of a coin . `dp[i][jcoins[i1]]` 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[i1]`. 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[i1] >= 0) dp[i][j] = dp[i  1][j] + dp[i][jcoins[i1]]; 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[i1] >= 0) dp[i][j] = dp[i  1][j] + dp[i][j  coins[i1]]; 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[i1][..]` 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[jcoins[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 ebooks ](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/fuckingalgorithm) 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