部分背包问题与贪心算法

梦里梦外; 2022-09-17 04:18 171阅读 0赞

题目描述：有一个背包，容量为 c，同时有若干物品，价值各不相同，重量也各不相同。我们需要选择一部分物品装入背包，要保证在不超过背包容量的前提下是的装入背包中的物品的总价值最大。与 0-1 背包不同的是，允许选择装入物品的一部分。比如选择 0.5 份的物品 A，或者选择 0.8 份的物品 B。

这种背包问题最经典的解法就是使用贪心算法来解决。具体操作过程和思想如下：

以上述问题为例，假如背包容量为 10，有 5 个物品可供选择，各个物品的重量和价值为：

![3d18addf9b6a4a94a18508fb36b3206f.jpg][]

那么，对于以上物品，我们应该首先选择将哪个物品装入背包呢？其实最简单的想法就是要不装价值最大的，要么装重量最小的，即要么装价值最大的物品 A，要么装重量最小的物品 D。但其实并不是这样的，我们需要根据物品的重量和价值首先去算出物品的“性价比”，即“重量 / 价值”，然后将性价比最高的一个物品第一个装入背包，然后选择性价比第二高的物品装入背包......以上五个物品的性价比分别是：

![b99a6a32df5943ca88acc7da8b7eb6fc.jpg][]

可以看到，性价比最高的是物品 D，所以我们先把物品 D 装入背包中

![9dd933dd69b3412e9920ff2ddfedde59.jpg][]

我们默认为背包的容量就是背包的重量，那么背包总容量为 10，即总承重为 10，装入了重量为 2 的物品 D 之后，剩余容量为 8。接下来我们将性价比第二高的物品 A 装入背包中

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54Sm5pyo55m9_size_12_color_FFFFFF_t_70_g_se_x_16][]

此时，背包容量仅剩余 4，而下一个待装入背包的物品是物品 E，但此时物品 E 的容量是 5，并不能完全装入背包中。而题目中允许装入部分物品，所以我们选择装入 0.8 份的物品 E

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54Sm5pyo55m9_size_12_color_FFFFFF_t_70_g_se_x_16 1][]

此时，背包已装满，总容量 10，总价值为 6 + 9 + 4 = 19。

以上便是部分背包问题的解决方法。相关的代码实现为：

public class PartPackages {
    
        public static BigDecimal getHighestValue(int capacity, int[] weights,int[] values) {
    
            // 创建物品列表并按照性价比倒序
            List<Item> itemList = new ArrayList<>();
            for(int i=0; i < weights.length; i++) {
                itemList.add(new Item(weights[i], values[i]));
            }
            itemList = itemList.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList());
    
            // 背包剩余容量
            int restCapacity = capacity;
            // 当前背包物品的最大价值
            BigDecimal highestValue = BigDecimal.ZERO;
    
            // 按照性价比从高到低选择物品
            for (Item item : itemList) {
                if (item.weight <= restCapacity) {
                    highestValue = highestValue.add(new BigDecimal(item.value));
                    restCapacity -= item.weight;
                } else {
                    // 背包装不下完整物品时，选择该件物品的一部分
                    BigDecimal partCapacity = new BigDecimal(restCapacity).divide(new BigDecimal(item.weight), 2, BigDecimal.ROUND_HALF_UP)
                            .setScale(2, BigDecimal.ROUND_HALF_UP);
                    highestValue = highestValue.add(partCapacity.multiply(new BigDecimal(item.value)));
                    break;
                }
            }
            return highestValue;
        }
    
        // 静态内部类 Item
        static class Item {
            private int weight;
            private int value;
            //物品的性价比
            private BigDecimal ratio;
    
            public Item (int weight, int value) {
                this.weight = weight;
                this.value = value;
                // 性价比 = 价值 / 重量
                this.ratio = new BigDecimal(value).divide(new BigDecimal(weight), 2, BigDecimal.ROUND_HALF_UP).setScale(2, BigDecimal.ROUND_HALF_UP);
            }
    
            public BigDecimal getRatio() {
                return ratio;
            }
        }
    
        public static void main(String[] args) {
            int capacity = 10;
            int[] weights = {4, 6, 3, 2, 5};
            int[] values = {9, 3, 1, 6, 5};
            System.out.println("背包最大价值：" + getHighestValue(capacity, weights, values));
        }
    
    }

在代码中，我们使用了静态内部类 Item 来更方便地记录物品的重量、价值以及性价比，而且也更容易去按照性价比去排序。

假如背包容量为 20，有 6 个物品，A、B、C、D、E、F，重量分别是 \{4，8，3，6，5，4\}，价值分别是 \{8，2，4，6，4，3\}，那么最终装入背包中的物品就是全部的物品 A + 全部的物品 C + 全部的物品 D + 全部的物品 E + 0.5 份的物品 F，其总价值 = 8 + 4 + 6 + 4 + 1.5 = 23.5。

以上便是部分背包问题的贪心算法的解答，还有一种 0-1 背包问题，我们需要使用动态规划方法去解答，在下一篇文章中说明~

此篇文章参考自《程序员小灰》的系列文章：[漫画：什么是“贪心算法”？如何求解“部分背包问题”？][Link 1]

[3d18addf9b6a4a94a18508fb36b3206f.jpg]: /images/20220828/3324ffb3332c4e2cb818b2876486d13d.png
[b99a6a32df5943ca88acc7da8b7eb6fc.jpg]: /images/20220828/c5285db470cc40cbbdeecc9ddf77f29d.png
[9dd933dd69b3412e9920ff2ddfedde59.jpg]: /images/20220828/d3590e196f1840e5b3259109267ed3ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54Sm5pyo55m9_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/152f7c082a1844e48c232fab65778b6d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54Sm5pyo55m9_size_12_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/de3f1d292b1643738a2ef06f577a0c41.png
[Link 1]: https://mp.weixin.qq.com/s/2vCnAOidBHu8y8MCMgBLTA