2023年8月1日发(作者：)
动态规划问题——完全背包（Java实现）1、问题描述已知：有N种物品和⼀个容量为V 的背包，每种物品都有⽆限件可⽤。放⼊第i种物品的耗费的空间是C[i]，得到的价值是W[i]。求解：将哪些物品装⼊背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最⼤？2、基本思路这个问题与01背包问题⾮常类似，不同的是每件物品有⽆限件。从每件物品的⾓度来看，它相关的策略并⾮取或者不取，⽽是有取0件、取1件、取2件... 直⾄取 V/C[i] 等很多种。如果按照01背包的思路，⽤⼆维数组F[i ][ v] 表⽰ 前i件物品恰放⼊⼀个容量恰为v的背包可以获得的最⼤价值，则状态转移⽅程为：使⽤⼆维数组的代码如下：package pack9jiang;import r;/** * 完全背包问题,基本思路，时间复杂度较⾼，使⽤⼆维数组 */public class CompletePackExtend2 { // N表⽰物体的个数，V表⽰背包的载重 int N,V; //⽤于存储每个物体的重量，下标从1开始 private int[] weight; //存储每个物体的收益，下标从1开始 private int[] value; //降成⼆维数组，⽤来保存每种状态下的最⼤收益 private int[][] F; public void CompletePackNonRecursive() { //对⼆维数组F进⾏初始化 for(int i = 0; i <= V; i++) { F[0][i] = 0; } //注意边界问题，i是从1开始的 for(int i = 1; i <= N; i++) { //j是正序、降序没影响 for (int j = 0; j <= V; j++) { for (int k = 0; k <= V / weight[i]; k++) { if (j >= k * weight[i]) { //注意：状态转移⽅程是F[i][j]，⽽不是F[i - 1][j] //因为这时放k个第i个物品，之后还可能继续放这个物体，所以应是F[i][j] F[i][j] = (F[i - 1][j - k * weight[i]] + k * value[i], F[i][j]); } else { //可以省略，这⾥为什么不是F[i - 1][j] //因为刚开始k=0，j >= 0 * weight[i]肯定成⽴，此时F[i][j] = F[i - 1][j]。 F[i][j] = F[i][j]; } } } } //打印所有结果，我们要求的是F[N][V] for(int i = 0; i <= N; i++) { for(int j = 0; j <= V; j++) { for(int j = 0; j <= V; j++) { (F[i][j] + " "); } n(); } } /** * 输⼊格式： 5 10 2 2 6 5 4 6 3 5 4 6 result:30 * 第⼀⾏是物体个数、背包总空间； * 第⼆⾏是每个物体的空间； * 第三⾏是每个物体的收益。 */ public void init() { Scanner sc = new Scanner(); N = t(); V = t(); //下标从1开始，表⽰第1个物品 weight = new int[N + 1]; value = new int[N + 1]; F= new int[N + 1][V + 1]; for(int i = 1; i <= N; i++) { weight[i] = t(); } for(int i = 1; i <= N; i++) { value[i] = t(); } } public static void main(String[] args) { CompletePackExtend2 cpe2 = new CompletePackExtend2(); (); tePackNonRecursive(); }}也可以⽤⼀维数组来优化空间开销，⽤⼀维数组的代码实现如下:package pack9jiang;import r;/** * 完全背包问题，基本解决思路，但是时间复杂度过⾼ */public class CompletePack { // N表⽰物体的个数，V表⽰背包的载重 int N,V; //⽤于存储每个物体的重量，下标从1开始 private int[] weight; //存储每个物体的收益，下标从1开始 private int[] value; //降成⼀维数组，⽤来保存每种状态下的最⼤收益 private int[] F;
public void CompletePackNonRecursive() { //对⼀维数组F进⾏初始化 //对⼀维数组F进⾏初始化 for(int i = 0; i <= V; i++) { F[i] = 0; } //注意边界问题，i是从1开始的 for(int i = 1; i <= N; i++) { for(int j = V; j >= 0; j--) { for(int k = 1; k <= V/weight[i]; k++) { if(j >= k * weight[i]) { F[j] = (F[j - k * weight[i]] + k * value[i], F[j]); }else { //可以省略 F[j]= F[j]; } } } } //打印所有结果，我们要求的是F[V] for(int i = 0; i <= V; i++) { (F[i] + " "); } n(); } /** * 输⼊格式： 5 10 2 2 6 5 4 6 3 5 4 6 result:30 * 第⼀⾏是物体个数、背包总空间； * 第⼆⾏是每个物体的空间； * 第三⾏是每个物体的收益。 */ public void init() { Scanner sc = new Scanner(); N = t(); V = t(); //下标从1开始，表⽰第1个物品 weight = new int[N + 1]; value = new int[N + 1]; F= new int[V + 1];//注意是 V + 1 for(int i = 1; i <= N; i++) { weight[i] = t(); } for(int i = 1; i <= N; i++) { value[i] = t(); } } public static void main(String[] args) { CompletePack cp = new CompletePack(); (); tePackNonRecursive(); }}分析算法复杂度：程序需要求解N*V个状态，每⼀个状态需要求出的时间为O(V/weight[i])，总的时间复杂度为O(NV*∑(V/weight[i]))。⼀个简单有效的代码优化：若两件物品i、j满⾜value[i] <= value[j] 且 weight[i] >= weight[j]，则可以将物品j直接去掉，不予考虑。即，如果⼀个物品A占空间少且价值⾼，⽽物品B占空间多但价值不⾼，那么肯定优先考虑物品A的。对于随机⽣成的数据，这个⽅法往往能⼤⼤减少物品的件数，从⽽加快速度。但是在最快情况下，可能⼀件物品也去不掉，这个优化可以简单的⽤O(n^2)地实现，⼀般能承受。========================代码待添加========================3、转化为01背包问题求解思路⼀：完全背包的物品可以取⽆限件，我们直接改变第i件物品的总个数，使之达到 V/weight[i] 件，之后直接利⽤01背包的思路进⾏求解。时间复杂度分析：这种⽅法完全没有改进时间复杂度，因为拆分后的物品总数量很⼤，时间复杂度为O(V * ∑(V/weight[i]))思路⼆：采⽤⼆进制的思想对物品进⾏拆分，可以减少拆分物品的总数量。具体思路：把第i中物品拆分成费⽤为weight[i]*（2^k）、价值为value[i]*（2^k）的若⼲件物品，其中k满⾜weight[i]*（2^k） <= V，其中k从0开始取值。时间复杂度分析：拆分后的物品总数量为num = ∑ log(V/weight[i]),所以时间复杂度为 O(V * num)举例分析：假设A物品的空间为2，价值为3，背包的总空间为20。根据思路⼀拆分：可以拆分成10个物品，每个物品的空间为2，价值为3；根据思路⼆拆分：可以拆分为4种物品，分别是物品⼀（空间2*1，价值为3）、物品⼆（空间2*2，价值为6）、物品三（空间2*4，价值为12）、物品⼀（空间2*8，价值为24）。⽤这4个物品就可以表⽰思路⼀10个物品的所有情况，且⼤⼤减少了拆分物品的数量。思路⼆的代码如下：=========================4、⼀种O(V*N)的算法（最优的解法）这种算法使⽤了⼀维数组，伪代码如下：发现：与01背包的⼀维的伪代码相⽐，这个伪代码仅仅只是内循环中v的循环次序不同⽽已。那么为什么这个算法可⾏呢？考虑01背包中为什么要按照v递减的次序循环（回顾之前的），这是为了保证在第i次循环更新F[v]之前，要⽤到的F[v-weight[i]]和F[v]都是第i-1次循环更新的值，还未进⾏第i次循环的更新以确保正确。那么考虑完全背包问题，完全背包的特点是每种物品可以选⼊⽆限件，所以在考虑“加选⼀件第i种物品”这种策略时，正需要⼀个可能已经选择过第i种物品的⼦结果F[v-weight[i]]和F[v]，所以就可以且必须采⽤v递增的顺序循环。代码如下：package pack9jiang;import r;/** * 完全背包问题，时间复杂度为O(NV)的算法 * 与01背包的⼀维数组基本⼀样，唯⼀不同的就是v的遍历顺序是相反的 */public class CompletePackExtend1 { // N表⽰物体的个数，V表⽰背包的载重 int N,V; //⽤于存储每个物体的重量，下标从1开始 private int[] weight; //存储每个物体的收益，下标从1开始 private int[] value; //降成⼀维数组，⽤来保存每种状态下的最⼤收益 private int[] F; public void CompletePackNonRecursive() { //对⼀维数组F进⾏初始化 for(int i = 0; i <= V; i++) { F[i] = 0; } //注意边界问题，i是从1开始的 for(int i = 1; i <= N; i++) { //唯⼀不同的地⽅，j是正序遍历 for(int j = 0; j <= V; j++) { if(j >= weight[i]) { F[j] = (F[j - weight[i]] + value[i], F[j]); }else { //可以省略 F[j]= F[j]; } } } //打印所有结果，我们要求的是F[V] for(int i = 0; i <= V; i++) { (F[i] + " "); } n(); } /** * 输⼊格式： 5 10 2 2 6 5 4 6 3 5 4 6 result:30 * 第⼀⾏是物体个数、背包总空间； * 第⼆⾏是每个物体的空间； * 第三⾏是每个物体的收益。 */ public void init() { Scanner sc = new Scanner(); N = t(); V = t(); //下标从1开始，表⽰第1个物品 weight = new int[N + 1]; value = new int[N + 1]; F= new int[V + 1];//注意是 V + 1 for(int i = 1; i <= N; i++) { weight[i] = t(); } for(int i = 1; i <= N; i++) { value[i] = t(); } } public static void main(String[] args) { CompletePackExtend1 cpe1 = new CompletePackExtend1(); (); tePackNonRecursive(); }}
2023年8月1日发(作者：)
动态规划问题——完全背包（Java实现）1、问题描述已知：有N种物品和⼀个容量为V 的背包，每种物品都有⽆限件可⽤。放⼊第i种物品的耗费的空间是C[i]，得到的价值是W[i]。求解：将哪些物品装⼊背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最⼤？2、基本思路这个问题与01背包问题⾮常类似，不同的是每件物品有⽆限件。从每件物品的⾓度来看，它相关的策略并⾮取或者不取，⽽是有取0件、取1件、取2件... 直⾄取 V/C[i] 等很多种。如果按照01背包的思路，⽤⼆维数组F[i ][ v] 表⽰ 前i件物品恰放⼊⼀个容量恰为v的背包可以获得的最⼤价值，则状态转移⽅程为：使⽤⼆维数组的代码如下：package pack9jiang;import r;/** * 完全背包问题,基本思路，时间复杂度较⾼，使⽤⼆维数组 */public class CompletePackExtend2 { // N表⽰物体的个数，V表⽰背包的载重 int N,V; //⽤于存储每个物体的重量，下标从1开始 private int[] weight; //存储每个物体的收益，下标从1开始 private int[] value; //降成⼆维数组，⽤来保存每种状态下的最⼤收益 private int[][] F; public void CompletePackNonRecursive() { //对⼆维数组F进⾏初始化 for(int i = 0; i <= V; i++) { F[0][i] = 0; } //注意边界问题，i是从1开始的 for(int i = 1; i <= N; i++) { //j是正序、降序没影响 for (int j = 0; j <= V; j++) { for (int k = 0; k <= V / weight[i]; k++) { if (j >= k * weight[i]) { //注意：状态转移⽅程是F[i][j]，⽽不是F[i - 1][j] //因为这时放k个第i个物品，之后还可能继续放这个物体，所以应是F[i][j] F[i][j] = (F[i - 1][j - k * weight[i]] + k * value[i], F[i][j]); } else { //可以省略，这⾥为什么不是F[i - 1][j] //因为刚开始k=0，j >= 0 * weight[i]肯定成⽴，此时F[i][j] = F[i - 1][j]。 F[i][j] = F[i][j]; } } } } //打印所有结果，我们要求的是F[N][V] for(int i = 0; i <= N; i++) { for(int j = 0; j <= V; j++) { for(int j = 0; j <= V; j++) { (F[i][j] + " "); } n(); } } /** * 输⼊格式： 5 10 2 2 6 5 4 6 3 5 4 6 result:30 * 第⼀⾏是物体个数、背包总空间； * 第⼆⾏是每个物体的空间； * 第三⾏是每个物体的收益。 */ public void init() { Scanner sc = new Scanner(); N = t(); V = t(); //下标从1开始，表⽰第1个物品 weight = new int[N + 1]; value = new int[N + 1]; F= new int[N + 1][V + 1]; for(int i = 1; i <= N; i++) { weight[i] = t(); } for(int i = 1; i <= N; i++) { value[i] = t(); } } public static void main(String[] args) { CompletePackExtend2 cpe2 = new CompletePackExtend2(); (); tePackNonRecursive(); }}也可以⽤⼀维数组来优化空间开销，⽤⼀维数组的代码实现如下:package pack9jiang;import r;/** * 完全背包问题，基本解决思路，但是时间复杂度过⾼ */public class CompletePack { // N表⽰物体的个数，V表⽰背包的载重 int N,V; //⽤于存储每个物体的重量，下标从1开始 private int[] weight; //存储每个物体的收益，下标从1开始 private int[] value; //降成⼀维数组，⽤来保存每种状态下的最⼤收益 private int[] F;
public void CompletePackNonRecursive() { //对⼀维数组F进⾏初始化 //对⼀维数组F进⾏初始化 for(int i = 0; i <= V; i++) { F[i] = 0; } //注意边界问题，i是从1开始的 for(int i = 1; i <= N; i++) { for(int j = V; j >= 0; j--) { for(int k = 1; k <= V/weight[i]; k++) { if(j >= k * weight[i]) { F[j] = (F[j - k * weight[i]] + k * value[i], F[j]); }else { //可以省略 F[j]= F[j]; } } } } //打印所有结果，我们要求的是F[V] for(int i = 0; i <= V; i++) { (F[i] + " "); } n(); } /** * 输⼊格式： 5 10 2 2 6 5 4 6 3 5 4 6 result:30 * 第⼀⾏是物体个数、背包总空间； * 第⼆⾏是每个物体的空间； * 第三⾏是每个物体的收益。 */ public void init() { Scanner sc = new Scanner(); N = t(); V = t(); //下标从1开始，表⽰第1个物品 weight = new int[N + 1]; value = new int[N + 1]; F= new int[V + 1];//注意是 V + 1 for(int i = 1; i <= N; i++) { weight[i] = t(); } for(int i = 1; i <= N; i++) { value[i] = t(); } } public static void main(String[] args) { CompletePack cp = new CompletePack(); (); tePackNonRecursive(); }}分析算法复杂度：程序需要求解N*V个状态，每⼀个状态需要求出的时间为O(V/weight[i])，总的时间复杂度为O(NV*∑(V/weight[i]))。⼀个简单有效的代码优化：若两件物品i、j满⾜value[i] <= value[j] 且 weight[i] >= weight[j]，则可以将物品j直接去掉，不予考虑。即，如果⼀个物品A占空间少且价值⾼，⽽物品B占空间多但价值不⾼，那么肯定优先考虑物品A的。对于随机⽣成的数据，这个⽅法往往能⼤⼤减少物品的件数，从⽽加快速度。但是在最快情况下，可能⼀件物品也去不掉，这个优化可以简单的⽤O(n^2)地实现，⼀般能承受。========================代码待添加========================3、转化为01背包问题求解思路⼀：完全背包的物品可以取⽆限件，我们直接改变第i件物品的总个数，使之达到 V/weight[i] 件，之后直接利⽤01背包的思路进⾏求解。时间复杂度分析：这种⽅法完全没有改进时间复杂度，因为拆分后的物品总数量很⼤，时间复杂度为O(V * ∑(V/weight[i]))思路⼆：采⽤⼆进制的思想对物品进⾏拆分，可以减少拆分物品的总数量。具体思路：把第i中物品拆分成费⽤为weight[i]*（2^k）、价值为value[i]*（2^k）的若⼲件物品，其中k满⾜weight[i]*（2^k） <= V，其中k从0开始取值。时间复杂度分析：拆分后的物品总数量为num = ∑ log(V/weight[i]),所以时间复杂度为 O(V * num)举例分析：假设A物品的空间为2，价值为3，背包的总空间为20。根据思路⼀拆分：可以拆分成10个物品，每个物品的空间为2，价值为3；根据思路⼆拆分：可以拆分为4种物品，分别是物品⼀（空间2*1，价值为3）、物品⼆（空间2*2，价值为6）、物品三（空间2*4，价值为12）、物品⼀（空间2*8，价值为24）。⽤这4个物品就可以表⽰思路⼀10个物品的所有情况，且⼤⼤减少了拆分物品的数量。思路⼆的代码如下：=========================4、⼀种O(V*N)的算法（最优的解法）这种算法使⽤了⼀维数组，伪代码如下：发现：与01背包的⼀维的伪代码相⽐，这个伪代码仅仅只是内循环中v的循环次序不同⽽已。那么为什么这个算法可⾏呢？考虑01背包中为什么要按照v递减的次序循环（回顾之前的），这是为了保证在第i次循环更新F[v]之前，要⽤到的F[v-weight[i]]和F[v]都是第i-1次循环更新的值，还未进⾏第i次循环的更新以确保正确。那么考虑完全背包问题，完全背包的特点是每种物品可以选⼊⽆限件，所以在考虑“加选⼀件第i种物品”这种策略时，正需要⼀个可能已经选择过第i种物品的⼦结果F[v-weight[i]]和F[v]，所以就可以且必须采⽤v递增的顺序循环。代码如下：package pack9jiang;import r;/** * 完全背包问题，时间复杂度为O(NV)的算法 * 与01背包的⼀维数组基本⼀样，唯⼀不同的就是v的遍历顺序是相反的 */public class CompletePackExtend1 { // N表⽰物体的个数，V表⽰背包的载重 int N,V; //⽤于存储每个物体的重量，下标从1开始 private int[] weight; //存储每个物体的收益，下标从1开始 private int[] value; //降成⼀维数组，⽤来保存每种状态下的最⼤收益 private int[] F; public void CompletePackNonRecursive() { //对⼀维数组F进⾏初始化 for(int i = 0; i <= V; i++) { F[i] = 0; } //注意边界问题，i是从1开始的 for(int i = 1; i <= N; i++) { //唯⼀不同的地⽅，j是正序遍历 for(int j = 0; j <= V; j++) { if(j >= weight[i]) { F[j] = (F[j - weight[i]] + value[i], F[j]); }else { //可以省略 F[j]= F[j]; } } } //打印所有结果，我们要求的是F[V] for(int i = 0; i <= V; i++) { (F[i] + " "); } n(); } /** * 输⼊格式： 5 10 2 2 6 5 4 6 3 5 4 6 result:30 * 第⼀⾏是物体个数、背包总空间； * 第⼆⾏是每个物体的空间； * 第三⾏是每个物体的收益。 */ public void init() { Scanner sc = new Scanner(); N = t(); V = t(); //下标从1开始，表⽰第1个物品 weight = new int[N + 1]; value = new int[N + 1]; F= new int[V + 1];//注意是 V + 1 for(int i = 1; i <= N; i++) { weight[i] = t(); } for(int i = 1; i <= N; i++) { value[i] = t(); } } public static void main(String[] args) { CompletePackExtend1 cpe1 = new CompletePackExtend1(); (); tePackNonRecursive(); }}
![[力扣]动态规划(DP)问题分类汇总](/uploads/image/0950.jpg)
发布评论