文档章节

关于01背包问题的优化

o
 osc_1ee7cxmx
发布于 2018/08/06 22:20
字数 1540
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、01背包问题介绍

  背包问题是经典的动态规划问题之一;

  常见的01背包问题就是说有一堆物品,现在要装入一个容器中,这些物品的重量和价值各不一致,而容器的重量又是有限的,没种物品只能装1个或者不装(0个),求当重量限定为w时,这些物品能装进去组合成的最高价值是多少?

 

分析:我们首先将物品排成一排(随机),依次标记为1号,2号。。。。然后从一号开始依次往里放,放的时候判断当前物品是不是应该放进去:

      如果当前物品放进去之后的最高总价值不放进去的最高总价值 大 ,那么就是要放入,然后总价值取放入之后的

                                  反之不放入,总价值依然取之前的值。

  并且,在对同一个物品判断时,从0依次增加容器的容量,直到上限w

     当前物品放进去之后的最高总价值 = 上一号物品判断时(容量 = 当前容量 - 当前物品重量 时)总价值 + 当前物品的价值

     不放进去的最高总价值 = 上一号物品判断的时候(容量 = 当前容量 时)总价值

  所以有伪代码如下:

if (当前物品重量 > 当前容量) {
            此时最高总价值 = 当前物品不放进去的最高总价值;  // 此时物品重量比容量大,放不进去,只能取放不进去的情况
        } else {
            此时最高总价值 = max(当前物品不放进去的最高总价值, 当前物品放进去的最高总价值);
        }

因此,我们可以用一个状态表来对整个过程进行描述。

假设现在是有三物品 (不是三种)一号、二号、三号,重量分别为3,2,5; 价值分别为7,4,8; 当前容器容量为8,求最大价值。

首先,第一行,为没有任何物品的时候,全部置0;

第二行,判断一号物品能不能放:

  当容量扩充为3的时候,一号物品终于能放,价值为7,由于当前也只有一号,所以后面都是7;

第三行,判断二号物品能不能放:

  当容量扩充为2的时候,二号物品终于能放,价值为4,与不放进去的最高价值(一号物品在此容量时的值:0)进行比较,所以成功放进去;

  当容量扩充为3的时候,二号物品一定放时,价值为4,与不放进去的最高价值(一号物品在此容量时的值:7)进行比较,决定不放进去了;

  。。。

  当容量扩充为5的时候,二号物品一定放时,最高价值为(一号物品在(当前容量 - 二号物品的重量)时的价值+二号物品的价值

                                          =(一号物品在容量为(5-2)的时候 + 二号物品的价值)= 7 + 4 =11

  。。。【如下表】

容量 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0
一号 0 0 0 7 7 7 7 7 7
二号 0 0 4 7 7 11 11 11 11
三号 0 0 4 7 7 11 11 12 15

所以有代码如下:

public static int getMaxValue(int[] weight, int[] value, int w) {
        int n = weight.length;
        int[][] table = new int[n + 1][w + 1];
        for (int i = 1; i <= n; i++) {     // 物品遍历(第0行肯定全是0,所以不用遍历)
            for (int j = 0; j <= w; j++) { // 背包大小递增
                if (weight[i-1] > j) {     // 当前物品i的重量比背包容量j大,装不下,只能是不装
                    table[i][j] = table[i - 1][j];
                } else {                   // 装得下,Max{不装物品i, 装物品i}
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i-1]] + value[i-1]);
                }
            }
        }
        return table[n][w];
    }

提问:为什么要【n+1】行?

 ——因为之后每一个数都需要与上一行做比较,一号物品放入的时候也需要与没放入的时候做比较,所以空出一行作为“没有物品的时候”;

  为什么要【w+1】列?

 ——因为在容量递增时,第一个物品能放的时候,需要与容量减去当前物品的重量,也就是容量为0的时候做比较,所以,也是需要一列作为“0容量的时候”;

  为什么是weight[i - 1] 和 value[i - 1]?

    ——因为传入的重量和价值必然是从一号物品开始,而我们的表是从“没有物品”和“0容量”开始,多了一行和一列,所以 i 是当前物品的标号,而当前物品下标为【标号-1】;

 

二、空间复杂度优化

  很显然,上面算法的空间复杂度为矩阵大小【n+1】*【w+1】。

  n可能不大,但是实际应用伤的w可能会很大,这样造成了比较大的空间占用。

  而仔细观察发现,矩阵中的值只与当前值的左上角的矩阵里的值有关,如图二号物品容量为4时的价值7,只与绿色标注值有关。

容量 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0
一号 0 0 0 7 7 7 7 7 7
二号 0 0 4 7 7 11 11 11 11
三号 0 0 4 7 7 11 11 12 15

  并且我们是按行进行更新的,所以我们用一个一维数据就能进行状态的更替,不过要注意更新的方向。

  所以依赖关系为:下面依赖上面,右边依赖左边

  如果正常地从左到右边,那么右边面等待更新的值需要的依赖(左边)就会被覆盖掉,所以应该每行从右边开始更新。代码如下:

public static int getMaxValueByOne(int[] weight, int[] value, int w) {
        int n = weight.length;
        int[] table = new int[w + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = w; j >= 0; j--) {
                if (weight[i-1] <= j) {
                    table[j] = Math.max(table[j], table[j - weight[i-1]] + value[i-1]);
                }
            }
        }
        return table[w];
    }

  如此一来,01背包的空间复杂度就降为了O(w)

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

如果你失明了,你怎么编程? - How can you program if you're blind?

问题: Sight is one of the senses most programmers take for granted. 视觉是大多数程序员认为理所当然的感官之一。 Most programmers would spend hours looking at a computer monitor......

技术盛宴
12分钟前
4
0
如何删除使用Python的easy_install安装的软件包? - How do I remove packages installed with Python's easy_install?

问题: Python's easy_install makes installing new packages extremely convenient. Python的easy_install使安装新包非常方便。 However, as far as I can tell, it doesn't implement th......

fyin1314
42分钟前
8
0
如何将逗号分隔的字符串转换为数组? - How to convert a comma separated string to an array?

问题: I have a comma separated string that I want to convert into an array, so I can loop through it. 我有一个逗号分隔的字符串,我想将其转换成数组,因此可以循环遍历它。 Is the...

富含淀粉
今天
13
0
深源恒际:担心个人身份被冒用?不存在!

本文作者:c****t 近日,苟晶被冒名顶替身份参加高考的事件在社会各界掀起广泛热议。事件调查结果公布后,舆论风向逆转,吃瓜群众认为当事人夸大其词消费了公众情绪,一边对当事人所遭遇的不...

百度开发者中心
昨天
5
0
CKEditor 5 + SpringBoot实战(三):SpringData JPA数据持久化

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部