0-1背包问题从不懂到运用

短命女 2024-04-18 16:07 47阅读 0赞

**一. 理解**

1.  0-1背包问题是个什么问题
    
    一个小偷带了一个只能容纳C的背包来店里偷东西，店里有n个商品，每个商品有重量和价值，n(w,v)  
    问小偷能偷到的最大价值
    
    推荐一个视频，看完了可以很好的理解什么是背包问题，以及解决背包问题的思路、思想
    
    [https://video.tudou.com/v/XMTc5MjQ3NTg5Mg==.html?\_\_fr=oldtd][https_video.tudou.com_v_XMTc5MjQ3NTg5Mg_.html_fr_oldtd]
2.  在视频里面主要就是学会思想，实际代码操作还是有点不同的，需要自己动手写一篇并加以理解
    
        /** * 使用二维数组接受每个结点的值，该节点表示容量为w时，第k个及之前的商品的最大价值；int[k][w] * @param weight 商品重量列表 * @param value 商品价值列表，所以这里weight和value的长度相等，一一对应 * @param cap 小偷所带背包的容量 * @return 小偷所能偷到的最大价值 */
            public int backpack(int[] weight, int[] value, int cap) { 
                int length = weight.length;
                int[][] ints = new int[length][cap + 1];
                // 填充第一行，因为后面的循环第一行无法计算到
                for (int i = 0; i <= cap; i++) { 
                    ints[0][i] = i < weight[0] ? 0 : value[0];
                }
                for (int i = 1; i < length; i++) { 
                    for (int j = 0; j <= cap; j++) { 
                        // 小偷的背包装不下
                        if (j < weight[i]) { 
                            ints[i][j] = ints[i - 1][j];
                        } else { 
                            // 小偷选择装不装该商品的两种情况
                            ints[i][j] = Math.max(ints[i - 1][j], ints[i - 1][j - weight[i]] + value[i]);
                        }
                    }
                }
                return ints[length - 1][cap];
            }
3.  优化，空间复杂度的优化：  
    将二维数组压缩成一维数组，利用记忆（一维数组存储的每行都会被替换掉）的特点  
    因为由前面的公式可以知道，求 F(i,j)=max( F(i-1,j) , F(i-1,j-w(i))+value(i) )，即需要知道上一行的两个数，j和j-w(i)  
    利用记忆的特点也就是，当前行的 本身 和 j-w(i) 两个数  
    一维代替二维，就是一维的多次复用  
    还有一点需要注意的是：替换的话，遍历每行的时候，必须从后往前，不然不会取到之前的值
    
        /** * 空间极致化，将二维数组压缩成一维数组，利用记忆（一维数组存储的每行都会被替换掉）的特点 * 因为由前面的公式可以知道，求 F(i,j)=max( F(i-1,j) , F(i-1,j-w(i))+value(i) )，即需要知道上一行的两个数 * 利用记忆的特点也就是，当前行的 本身 和 j-w(i) 两个数 * 一维代替二维，就是一维的多次复用 * 还有一点需要注意的是：替换的话，遍历每行的时候，必须从后往前，不然不会取到之前的值 */
            public int backpackByOneArray(int[] weight, int[] value, int cap) { 
                int length = weight.length;
                int[] ints = new int[cap + 1];    
                for (int i = 0; i < length; i++) { 
                    for (int j = cap; j >= weight[i]; j--) { 
                        ints[j] = Math.max(ints[j], ints[j - weight[i]] + value[i]);
                    }
                }
                return ints[cap];
            }

**二. 应用**

1. LeetCode算法题第416： 分割等和子集
    
    
    给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

问题转换：0-1背包问题，数组相当于商品，商品的重量和价值相等，背包的容量就是sum/2，看能不能求得出最大价值等于背包容量判断有没有指定和

/** * 这是我自己根据背包问题看出来的解法 */
        public boolean canPartition2(int[] nums) { 
            int sum = 0;
            for (int num : nums) { 
                sum += num;
            }
            // 奇数
            if ((sum & 1) == 1) { 
                return false;
            }
            sum = sum >> 1;
            // 问题转换：0-1背包问题，数组相当于商品，商品的重量和价值相等，背包的容量就是sum，看能不能求得出最大价值等于背包容量判断有没有指定和
            int length = nums.length;
            int[] ints = new int[sum + 1];  
            for (int i = 0; i < length; i++) { 
                for (int j = sum; j >= nums[i]; j--) { 
                    ints[j] = Math.max(ints[j], ints[j - nums[i]] + nums[i]);
                }
            }
            return ints[sum] == sum;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWppdWppdTMz_size_16_color_FFFFFF_t_70]  
还有一种更简洁的写法，

/** * 这是我自己根据背包问题看出来的解法 */
        public boolean canPartition2(int[] nums) { 
            int sum = 0;
            for (int num : nums) { 
                sum += num;
            }
            // 奇数
            if ((sum & 1) == 1) { 
                return false;
            }
            sum = sum >> 1;
            // 问题转换：0-1背包问题，数组相当于商品，商品的重量和价值相等，背包的容量就是sum，看是否可以刚好装满背包
            boolean[] result = new boolean[sum + 1];
            // 背包容量为0的时候，肯定是true，因为可以什么都不装（刚好装满）
            result[0] = true;
            for (int num : nums) { 
                for (int j = sum; j >= num; j--) { 
                    // 容量为j的时候，是否可以刚好装满，两种情况：1.不装当前数，2.装当前数；两种情况下，只需要满足一种，即可达到要求
                    result[j] = result[j] || result[j - num];
                }
            }
            return result[sum];

1.  `给定一个整数数组和一个整数，问能否在数组中找到任意数之和等于该整数（每个数只能用一次）`  
    问题转换：背包问题，数组相当于商品，商品的价格和重量相等（为数组的值），待求和的整数相当于背包容量  
    最后：看求出来的最大价值跟背包容量是否一致即可判断
    
        /** * 问题转换：背包问题，数组相当于商品，商品的价格和重量相等（为数组的值），待求和的整数相当于背包容量 * 最后：看求出来的最大价值跟背包容量是否一致即可判断 */
            public boolean ifCanFindArraySum(int[] nums, int sum) { 
                if (nums == null || nums.length == 0) { 
                    return false;
                }
                int[] result = new int[sum + 1];
                for (int num : nums) { 
                    for (int j = sum; j >= num; j--) { 
                        // 两种情况
                        result[j] = Math.max(result[j], result[j - num] + num);
                    }
                }
                return result[sum] == sum;
            }
    
    其实跟LeetCode那一题很相似  
    第二种写法类似
2.  `给定一个整数数组和一个整数，问在数组中任意数之和等于该整数的组合方式有多少种（每个数只能用一次）`  
    转换为：背包问题，背包容量sumP，数组元素商品，元素值商品重量，求刚好装满背包的商品组合数
    
        public int findTargetSumWays(int[] nums, int sum) { 
                int[] result = new int[sum + 1];
                // 和等于0有一种方式
                result[0] = 1;
                for (int num : nums) { 
                    for (int j = sum; j >= num; j--) { 
                        // 和等于j：两种情况，1.不需要当前数，2.需要当前数（和等于j-当前数）
                        result[j] += result[j - num];
                    }
                }
                return result[sum];
            }
3.  背包问题总结：

/** * 背包问题，其实是一类问题（要不要当前数，背包容量转数组），并不是局限于求最大价值（数组形式不局限）， * 使用的时候关键是要找到递归的条件，即要不要当前数的两种情况该怎么组和成结果 * 如： * 最大价值，max（两种情况） * 是否可以刚好装满：||（两种情况） * 刚好装满的组合数：+（两种情况） */

遇到时还需要灵活运用

[https_video.tudou.com_v_XMTc5MjQ3NTg5Mg_.html_fr_oldtd]: https://video.tudou.com/v/XMTc5MjQ3NTg5Mg==.html?__fr=oldtd
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWppdWppdTMz_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8952cb6e1cc64f049098869dd593e56e.png