2023年8月1日发(作者：)

【算法】动态规划，解决背包问题（knapsack）（⼩偷是不是也得学⼀学动态规划啦哈哈）⼤家好，我是被⽩菜拱的猪。⼀个热爱学习废寝忘⾷头悬梁锥刺股，痴迷于girl的潇洒从容淡然coding handsome boy。⽂章⽬录⼀、写在前⾔常见算法思想第⼆谈—动态规划。⼆、动态规划（⼀）概念介绍动态规划（Dynamic Programmming）是将⼤问题拆解成⼩问题，然后⼀步步获得最优解的办法。看到这⾥我们不免产⽣疑惑，这不是与前⾯讲的分治算法⼀样嘛，都是将⼤问题拆分成⼩问题，他们的区别就是分值算法拆出的⼩问题是相互独⽴的，⼩问题的解不影响⼤问题的解，⽽动态规划经过分解的⼦问题不是相互独⽴的，它下⼀阶段的解是建⽴在上⼀阶段解的基础上进⼀步求解。所以称之为动态规划，它的解在动态的变化。解决动态规划问题可以通过画图填表的⽅式来推导出最优解。（⼆）01背包问题1、场景再现背包问题是动态规划的典型问题，我们通过解决该问题来加深对动态规划的理解。背包问题开个玩笑讲就是⼩偷拿⼀个包去偷东西，包的容量是是不变的，每⼀件都东西有它的重量和价值，那么请问⼩偷怎么偷能让⾃⼰偷的东西价值最⼤，在这⾥背包问题⼜分为完全背包问题和01背包问题，完全背包问题就是每⼀件物品的数量是⽆限的，⽽01背包问题是每种物品只有⼀件。我们这⾥讲的是01背包问题。好我们再现⼀个场景，下⾯有四种商品。⼩偷的包容量为8，问⼩偷怎么偷的money最多。编号1234重量2345价值34262、思路讲解我们把该问题分为两部分，⼀是如何装东西，另⼀个是如何打印出装了那些东西（⽤了回溯）（1）偷东西我们画⼀个表格⼀步⼀步的来。⾸先假如只放第⼀个物品，背包从0-8，这⾥总共要考虑32种情况，让我们看⼀下具体怎么填写这个表格。假如看了上⾯的解题归纳还是没有理解，那我就⽤的⽩话在解释⼀遍，⾸先我们装⼀个物品，这时分两种情况，即不能装进去和能装进去，假如不能装进去那么此时最⼤的价值等于前⾯已经装过物品价值的总和。能装进去，下⾯就要看看我们装了这个物品之后是否导致包内的价值反⽽变低，因为有的商品可能是体积⼤，但是价值低，所以我们这就就要进⾏⽐较，装与不装前后的价值变化，前⾯不装是因为客观因素决定，包包没有空间了我们没有办法去装，此时能装但是不去装，他的价值跟前⾯讲的不装价值⼀样，那么能装我们去装这时我们该怎么去装呢？⾸先我们的已经确定了这个商品肯定要装进去的，所以我们看包包减去要装商品体积之后剩下的体积所能装的最⼤价值，这时从表格⾥⾯找就ok了，然后进⾏⽐较。下⾯根据这个思路去画⼀画表格，为了观察⽅便，我们把上⾯的表格在赋值⼀份。编号1234重量2345价值3426物品中的0代表啥也没装物品 背包容量我们设置两个⼀维数组分别表⽰物品的重量与价值，代码见代码实现。先在这⾥贴打印结果，是不是跟我们之前分析的⼀摸⼀样。（2）偷了什么东西我们知道了⼩偷⼀个⼩⼩的包包能装最⼤的价值，那么偷了什么东西我们还是不知道，那么我们怎么知道⼩偷偷了什么东西呢?我们采⽤回溯，就是倒着来，从右下⾓出发，根据装物品的过程，假如前n个物品与前n-1个物品的价值⼀样，说明该物品没有加⼊到背包，假如不⼀样就说明该物品加⼊到了背包，然后减去该物品的体积，在去判断。直到背包容量为0。最后查到2号和4号物品被偷了，具体的代码全都放在了下⾯。3、代码实现ok，有请我们的代码隆重登场。⼀定好好看哦。package c;import ;/** * @author: ljl * @date: 2020/9/3 18:17 * @description: 动态规划求解背包问题 */public class Knapsack { public static void main(String[] args) { Knapsack knapsack = new Knapsack(); Knapsack knapsack = new Knapsack(); c(); (); //从右下⾓开始查找 (4,8); } private int[] weight = {0,2,3,4,5}; private int[] value = {0,3,4,2,6}; private int[][] table = new int[][9]; //⽤来表⽰哪⼀个物品被装了进去 0-没有 1-有 private int[] product = new int[5]; public void dynamic() { //外层是商品的数量 for (int i = 1; i < 5; i++) { //⾥⾯是背包的数量,背包的容量为8 for (int j = 1; j < 9; j++) { //先判断是否能讲该商品装进去 if (weight[i] > j) { //装不进去,价值与前⾯n-1物品价值⼀样 table[i][j] = table[i-1][j]; }else { //能装进去，判断是否因加了使价值变⼩，取加不加两种情况的最⼤值 //table[i - 1][j - weight[i]] + value[i] 注意要好好理解这段代码所表达的意思 table[i][j] = (table[i-1][j],table[i - 1][j - weight[i]] + value[i]); } } } } //打印表格 public void print() { for (int i = 0; i < ; i++) { //⾥⾯是背包的数量,背包的容量为8 for (int j = 0; j < table[0].length; j++) { (table[i][j] + " "); } n(); } } //i，j指的是表的坐标 i指的是物品，j指的是宝宝的容量 public void find(int i,int j) { if (i == 0) { //就输出哪些装了哪些没装 //直接打印 n(ng(product)); return; } //然后去判断是否含有该物品 if (table[i][j] == table[i-1][j]) { //说明不含这个物品,设置为0 product[i] = 0; //然后继续查找 find(i - 1,j); } else { //要么⼤要么相等，不存在下⾯⽐上⾯⼩的情况，所以这⾥使⽤else //说明包含这个物品 product[i] = 1; //然后减去当前物品的容量继续查找 find(i - 1,j - weight[i]); } }}三、结束语写下此篇⽂字，看来⼩偷偷东西学学动态规划还是很有必要的哈哈哈哈哈哈，开个玩笑。

2023年8月1日发(作者：)

【算法】动态规划，解决背包问题（knapsack）（⼩偷是不是也得学⼀学动态规划啦哈哈）⼤家好，我是被⽩菜拱的猪。⼀个热爱学习废寝忘⾷头悬梁锥刺股，痴迷于girl的潇洒从容淡然coding handsome boy。⽂章⽬录⼀、写在前⾔常见算法思想第⼆谈—动态规划。⼆、动态规划（⼀）概念介绍动态规划（Dynamic Programmming）是将⼤问题拆解成⼩问题，然后⼀步步获得最优解的办法。看到这⾥我们不免产⽣疑惑，这不是与前⾯讲的分治算法⼀样嘛，都是将⼤问题拆分成⼩问题，他们的区别就是分值算法拆出的⼩问题是相互独⽴的，⼩问题的解不影响⼤问题的解，⽽动态规划经过分解的⼦问题不是相互独⽴的，它下⼀阶段的解是建⽴在上⼀阶段解的基础上进⼀步求解。所以称之为动态规划，它的解在动态的变化。解决动态规划问题可以通过画图填表的⽅式来推导出最优解。（⼆）01背包问题1、场景再现背包问题是动态规划的典型问题，我们通过解决该问题来加深对动态规划的理解。背包问题开个玩笑讲就是⼩偷拿⼀个包去偷东西，包的容量是是不变的，每⼀件都东西有它的重量和价值，那么请问⼩偷怎么偷能让⾃⼰偷的东西价值最⼤，在这⾥背包问题⼜分为完全背包问题和01背包问题，完全背包问题就是每⼀件物品的数量是⽆限的，⽽01背包问题是每种物品只有⼀件。我们这⾥讲的是01背包问题。好我们再现⼀个场景，下⾯有四种商品。⼩偷的包容量为8，问⼩偷怎么偷的money最多。编号1234重量2345价值34262、思路讲解我们把该问题分为两部分，⼀是如何装东西，另⼀个是如何打印出装了那些东西（⽤了回溯）（1）偷东西我们画⼀个表格⼀步⼀步的来。⾸先假如只放第⼀个物品，背包从0-8，这⾥总共要考虑32种情况，让我们看⼀下具体怎么填写这个表格。假如看了上⾯的解题归纳还是没有理解，那我就⽤的⽩话在解释⼀遍，⾸先我们装⼀个物品，这时分两种情况，即不能装进去和能装进去，假如不能装进去那么此时最⼤的价值等于前⾯已经装过物品价值的总和。能装进去，下⾯就要看看我们装了这个物品之后是否导致包内的价值反⽽变低，因为有的商品可能是体积⼤，但是价值低，所以我们这就就要进⾏⽐较，装与不装前后的价值变化，前⾯不装是因为客观因素决定，包包没有空间了我们没有办法去装，此时能装但是不去装，他的价值跟前⾯讲的不装价值⼀样，那么能装我们去装这时我们该怎么去装呢？⾸先我们的已经确定了这个商品肯定要装进去的，所以我们看包包减去要装商品体积之后剩下的体积所能装的最⼤价值，这时从表格⾥⾯找就ok了，然后进⾏⽐较。下⾯根据这个思路去画⼀画表格，为了观察⽅便，我们把上⾯的表格在赋值⼀份。编号1234重量2345价值3426物品中的0代表啥也没装物品 背包容量我们设置两个⼀维数组分别表⽰物品的重量与价值，代码见代码实现。先在这⾥贴打印结果，是不是跟我们之前分析的⼀摸⼀样。（2）偷了什么东西我们知道了⼩偷⼀个⼩⼩的包包能装最⼤的价值，那么偷了什么东西我们还是不知道，那么我们怎么知道⼩偷偷了什么东西呢?我们采⽤回溯，就是倒着来，从右下⾓出发，根据装物品的过程，假如前n个物品与前n-1个物品的价值⼀样，说明该物品没有加⼊到背包，假如不⼀样就说明该物品加⼊到了背包，然后减去该物品的体积，在去判断。直到背包容量为0。最后查到2号和4号物品被偷了，具体的代码全都放在了下⾯。3、代码实现ok，有请我们的代码隆重登场。⼀定好好看哦。package c;import ;/** * @author: ljl * @date: 2020/9/3 18:17 * @description: 动态规划求解背包问题 */public class Knapsack { public static void main(String[] args) { Knapsack knapsack = new Knapsack(); Knapsack knapsack = new Knapsack(); c(); (); //从右下⾓开始查找 (4,8); } private int[] weight = {0,2,3,4,5}; private int[] value = {0,3,4,2,6}; private int[][] table = new int[][9]; //⽤来表⽰哪⼀个物品被装了进去 0-没有 1-有 private int[] product = new int[5]; public void dynamic() { //外层是商品的数量 for (int i = 1; i < 5; i++) { //⾥⾯是背包的数量,背包的容量为8 for (int j = 1; j < 9; j++) { //先判断是否能讲该商品装进去 if (weight[i] > j) { //装不进去,价值与前⾯n-1物品价值⼀样 table[i][j] = table[i-1][j]; }else { //能装进去，判断是否因加了使价值变⼩，取加不加两种情况的最⼤值 //table[i - 1][j - weight[i]] + value[i] 注意要好好理解这段代码所表达的意思 table[i][j] = (table[i-1][j],table[i - 1][j - weight[i]] + value[i]); } } } } //打印表格 public void print() { for (int i = 0; i < ; i++) { //⾥⾯是背包的数量,背包的容量为8 for (int j = 0; j < table[0].length; j++) { (table[i][j] + " "); } n(); } } //i，j指的是表的坐标 i指的是物品，j指的是宝宝的容量 public void find(int i,int j) { if (i == 0) { //就输出哪些装了哪些没装 //直接打印 n(ng(product)); return; } //然后去判断是否含有该物品 if (table[i][j] == table[i-1][j]) { //说明不含这个物品,设置为0 product[i] = 0; //然后继续查找 find(i - 1,j); } else { //要么⼤要么相等，不存在下⾯⽐上⾯⼩的情况，所以这⾥使⽤else //说明包含这个物品 product[i] = 1; //然后减去当前物品的容量继续查找 find(i - 1,j - weight[i]); } }}三、结束语写下此篇⽂字，看来⼩偷偷东西学学动态规划还是很有必要的哈哈哈哈哈哈，开个玩笑。