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

python实现动态规划0-1背包问题⼀、动态规划算法介绍动态规划算法通常⽤于求解具有某种最优性质的问题。在这类问题中，可能会有许多可⾏解。每⼀个解都对应于⼀个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若⼲个⼦问题，先求解⼦问题，然后从这些⼦问题的解得到原问题的解。与分治法不同的是，适合于⽤动态规划求解的问题，经分解得到⼦问题往往不是互相独⽴的。若⽤分治法来解这类问题，则分解得到的⼦问题数⽬太多，有些⼦问题被重复计算了很多次。如果我们能够保存已解决的⼦问题的答案，⽽在需要时再找出已求得的答案，这样就可以避免⼤量的重复计算，节省时间。我们可以⽤⼀个表来记录所有已解的⼦问题的答案。不管该⼦问题以后是否被⽤到，只要它被计算过，就将其结果填⼊表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式 。动态规划的基本步骤如下：1.刻画⼀个最优解的结构特征；2.递归定义最优解的值；3.计算最优解的值，通常采⽤⾃底向上的⽅法。⼆、0-1背包问题的动态规划1、0-1背包问题描述：的总价值最⼤，并且物品的总重量不超出背包的容量（2）要求 装⼊的物品不能重复2、思路分析（1）要求达到的⽬标为 装⼊背包中的物品利⽤动态规划来解决,每次遍历到的第 i 个物品，根据 weight[i] 与 value[i] 来确定是否需要将该物品放⼊背包中。即对于给定的 n个物品，设 weight[i]、value[i] 分别为第 i 个物品的重量与价值，m 为背包的容量。再令 v[i][j] 表⽰在前 i 个物品中进⾏组合后装⼊容量为 j 的背包中的最⼤价值。则有下⾯的结果：(1) v[0][i] = v[i][0]=0; // 表⽰ 填⼊表 第⼀⾏和第⼀列都是 0(2) 当 weight[i] > j 时，v[i][j] = v[i-1][j]; // 当准备加⼊的新增的商品的重量⼤于当前背包的容量时，就直接使⽤上⼀个单元格的装⼊策略(3) 当 j >= weight[i-1] 时： v[i][j]=max{v[i-1][j], value[i] + v[i-1][j-weight[i]]} // 当准备加⼊的新增的商品的重量⼩于或者等于当前背包的容量时,使⽤的装⼊策略，各部分说明如下v[i-1][j]： 就是上⼀个单元格的装⼊的最⼤价值value[i] : 表⽰当前商品的价值v[i-1][j-weight[i]] ： 装⼊前 i-1 个商品，到剩余背包容量 j-weight[i] 的最⼤价值当 j >= weight[i] 时： v[i][j] = max{v[i-1][j], value[i]+v[i-1][j-weight[i]]} ;3、举个栗⼦ 如下填表⽅式，逐步推导，得到最优解⼆、python算法实现：def bag(n, c, w, v): """ 测试数据： n = 4 物品的数量， c = 10 书包能承受的重量， w = [5,4,6,3] 每个物品的重量， v = [10,40,30,40] 每个物品的价值 """ #

置零，表⽰初始状态 value = [[0 for j in range(c + 1)] for i in range(n + 1)] #表格为从c+1列 n+1⾏ for i in range(1, n + 1): #循环从第⼀⾏到n+1⾏ for j in range(1, c + 1): value[i][j] = value[i - 1][j] #

背包总容量够放当前物体，遍历前⼀个状态考虑是否置换 if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]: value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1] for x in value: print(x) return value输⼊测试数据，产⽣结果如图：2、输出背包⾥所放的物品，只需从尾遍历物品，当value⼤于上⼀⾏同样位置的value时，表⽰放进该物品。找出最⼤价值和放⼊背包的具体物品。def show(n, c, wi, value): print('最⼤价值为:', value[n][c]) x = [False for i in range(n)] w = c for i in range(n, 0, -1): if value[i][w] > value[i - 1][w]: x[i - 1] = True w -= wi[i - 1] print('背包中所装物品为:') for i in range(n): if x[i]: print('第', i+1, '个,', end='')结果如图所⽰：

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

python实现动态规划0-1背包问题⼀、动态规划算法介绍动态规划算法通常⽤于求解具有某种最优性质的问题。在这类问题中，可能会有许多可⾏解。每⼀个解都对应于⼀个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若⼲个⼦问题，先求解⼦问题，然后从这些⼦问题的解得到原问题的解。与分治法不同的是，适合于⽤动态规划求解的问题，经分解得到⼦问题往往不是互相独⽴的。若⽤分治法来解这类问题，则分解得到的⼦问题数⽬太多，有些⼦问题被重复计算了很多次。如果我们能够保存已解决的⼦问题的答案，⽽在需要时再找出已求得的答案，这样就可以避免⼤量的重复计算，节省时间。我们可以⽤⼀个表来记录所有已解的⼦问题的答案。不管该⼦问题以后是否被⽤到，只要它被计算过，就将其结果填⼊表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式 。动态规划的基本步骤如下：1.刻画⼀个最优解的结构特征；2.递归定义最优解的值；3.计算最优解的值，通常采⽤⾃底向上的⽅法。⼆、0-1背包问题的动态规划1、0-1背包问题描述：的总价值最⼤，并且物品的总重量不超出背包的容量（2）要求 装⼊的物品不能重复2、思路分析（1）要求达到的⽬标为 装⼊背包中的物品利⽤动态规划来解决,每次遍历到的第 i 个物品，根据 weight[i] 与 value[i] 来确定是否需要将该物品放⼊背包中。即对于给定的 n个物品，设 weight[i]、value[i] 分别为第 i 个物品的重量与价值，m 为背包的容量。再令 v[i][j] 表⽰在前 i 个物品中进⾏组合后装⼊容量为 j 的背包中的最⼤价值。则有下⾯的结果：(1) v[0][i] = v[i][0]=0; // 表⽰ 填⼊表 第⼀⾏和第⼀列都是 0(2) 当 weight[i] > j 时，v[i][j] = v[i-1][j]; // 当准备加⼊的新增的商品的重量⼤于当前背包的容量时，就直接使⽤上⼀个单元格的装⼊策略(3) 当 j >= weight[i-1] 时： v[i][j]=max{v[i-1][j], value[i] + v[i-1][j-weight[i]]} // 当准备加⼊的新增的商品的重量⼩于或者等于当前背包的容量时,使⽤的装⼊策略，各部分说明如下v[i-1][j]： 就是上⼀个单元格的装⼊的最⼤价值value[i] : 表⽰当前商品的价值v[i-1][j-weight[i]] ： 装⼊前 i-1 个商品，到剩余背包容量 j-weight[i] 的最⼤价值当 j >= weight[i] 时： v[i][j] = max{v[i-1][j], value[i]+v[i-1][j-weight[i]]} ;3、举个栗⼦ 如下填表⽅式，逐步推导，得到最优解⼆、python算法实现：def bag(n, c, w, v): """ 测试数据： n = 4 物品的数量， c = 10 书包能承受的重量， w = [5,4,6,3] 每个物品的重量， v = [10,40,30,40] 每个物品的价值 """ #

置零，表⽰初始状态 value = [[0 for j in range(c + 1)] for i in range(n + 1)] #表格为从c+1列 n+1⾏ for i in range(1, n + 1): #循环从第⼀⾏到n+1⾏ for j in range(1, c + 1): value[i][j] = value[i - 1][j] #

背包总容量够放当前物体，遍历前⼀个状态考虑是否置换 if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]: value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1] for x in value: print(x) return value输⼊测试数据，产⽣结果如图：2、输出背包⾥所放的物品，只需从尾遍历物品，当value⼤于上⼀⾏同样位置的value时，表⽰放进该物品。找出最⼤价值和放⼊背包的具体物品。def show(n, c, wi, value): print('最⼤价值为:', value[n][c]) x = [False for i in range(n)] w = c for i in range(n, 0, -1): if value[i][w] > value[i - 1][w]: x[i - 1] = True w -= wi[i - 1] print('背包中所装物品为:') for i in range(n): if x[i]: print('第', i+1, '个,', end='')结果如图所⽰：