xgqfrms

xgqfrms 查看完整档案

其它编辑清华大学  |  CS 编辑xgqfrms.xyz  |  CEO 编辑 ufo.xyz 编辑
编辑

I'm a Geeker!

个人动态

xgqfrms 赞了文章 · 2020-11-23

旗帜鲜明地抵制 CSDN 下载(盗版)站!

SegmentFault 上线付费课程以来,对于内容质量一直严格把关,讲师认真备课,课后为学员答疑,广受好评。然而近期有多位 SegmentFault 讲师反馈在 CSDN 下载频道出现了大量他的盗版课程。

clipboard.png

不查不知道,一查我们发现——我们讲师辛辛苦苦花了上百个小时录制的付费课程,在 CSDN 下载频道竟有满满一屏幕的盗版存在(相关证据我们已经找律师团队取证),同时根据他们的关键词推荐我们发现在其博客频道也有大量的盗版内容,防不胜防,让人不吐不快。

clipboard.png

昨天我在朋友圈公开这个事情后,收到了大量业内同行的反馈,我们发现不仅仅是 SegmentFault,几乎我认识的所有同行以及我们熟悉的讲师的付费内容(包括不限于课程、图书、专栏)都有被 CSDN 下载频道侵权的经历,昨天,我们用了同行的一些关键词在 CSDN 下载频道进行检索,同样发现存在有大量的盗版内容存在。

clipboard.png

同时我们也收到一些用户的反馈在 CSDN 下载频道有大量 IT 相关技术书籍的扫描版文件,毫无疑问都是盗版资源。上传时期从 2016 年(或者更早)开始到至今一直存在。

我们通过关键词在 Google 检索后,发现最早控诉 CSDN 下载频道的内容《CSDN 首页鼓励盗版图书下载》是在 2005 年发布,在知乎等社区也有大量的讨论,如《如何看待 CSDN 利用用户上传的盗版资料卖积分赚钱?》《为什么 CSDN 能做到让用户花钱买积分下载自己网站的盗版资源?》……可见已在业内引起公愤。

clipboard.png

CSDN 做为中国最早的技术社区之一,我们认可其对开发者之间线上交流做出的贡献,但是其下载频道的存在大大助长了大量盗版侵权内容的产生。并非个例,长期存在,越发泛滥,从未被解决——这代表其产品存在根本上的机制问题。

CSDN 官方对此不知情吗?

不过是睁一只眼闭一只眼罢了——CSDN 的下载频道占了总社区超过 30% 的流量。靠着盗版和侵权他人优质内容,获取平台流量,再依靠平台流量进行广告和其他形式的变现。这不是非法牟利是什么?

我们不禁质疑号称中国最大技术社区的 CSDN 究竟拥有怎样的价值观?

纵容盗版,非法牟利;

无视用户隐私——曾经明文存储用户名密码导致用户数据泄露;

甚至欺骗客户——夸大网站流量,广告数据造假。还记得去年程序员广告代码刷量的乌龙事件吗?“博客详情页PC增加广告系统刷量代码”这句话写在了代码注释里面上线了。原来客户的广告数据都是刷出来的?(心疼投放广告的客户)

其实技术圈子非常小,很多同行可能碍于面子或者各种各样的原因,没有公开地去声讨 CSDN,一些声讨可能也并没有解决问题,这更助长了其纵容盗版的气焰。 SegmentFault 作为技术社区的一员,我们深知社区发展的不易,我们有责任帮助我们的讲师维护其付费内容的版权不被侵犯。

我们已经聘请专业的律师团队取证,同时我们也呼吁被 CSDN 下载站侵犯过内容版权的同行,讲师,书籍作者,广大开发者一起发声,在评论区留下你的声音和被侵权经历,通过曝光侵权甚至违法行为,共同净化行业环境。

一起举报

到中央网信办(www.12377.cn)

国家新闻出版广电总局官网(www.sapprft.gov.cn)

举报 CSDN下载站的盗版侵权行为。

图片描述

SegmentFault CEO:高阳Sunny 2019年5月9日凌晨于北京

查看原文

赞 147 收藏 1 评论 59

xgqfrms 收藏了文章 · 2020-10-12

javascript背包问题详解

image_1c3ds1q091ubg5bm1gaj3vv1jm19.png-64.6kB

引子

打算好好学一下算法,先拿背包问题入手。但是网上许多教程都是C++或java或python,大部分作者都是在校生,虽然算法很强,但是完全没有工程意识,全局变量满天飞,变量名不明所以。我查了许多资料,花了一个星期才搞懂,最开始的01背包耗时最多,以前只会枚举(就是普通的for循环,暴力地一步步遍历下去),递归与二分,而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

01背包问题

篇幅可能有点长,但请耐心看一下,你会觉得物有所值的。本文以后还会扩展,因为我还没有想到完全背包与多重背包打印物品编号的方法。如果有高人知道,劳烦在评论区指教一下。

注意,由于社区不支持LaTex数学公式,你们看到${xxxx}$,就自己将它们过滤吧。

1.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品均只有一件,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

对于一种物品,要么装入背包,要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为01背包问题

1.2 问题分析:

数据:物品个数${n=5}$,物品重量${weights=[2,2,6,5,4]}$,物品价值${values=[6,3,5,4,6]}$,背包总容量${W=10}$。

我们设置一个矩阵${f}$来记录结果,${f(i, j)}$ 表示可选物品为 ${i...n}$ 背包容量为 ${j(0<=j<=W)}$ 时, 背包中所放物品的最大价值。

wvi\j012345678910
260
231
652
543
464

我们先看第一行,物品0的体积为2,价值为6,当容量为0时,什么也放不下,因此第一个格式只能填0,程序表示为${f(0,0) = 0}$或者${f[0][0] = 0}$。 当${j=1}$时,依然放不下${w_0}$,因此依然为0,${f(0, 1) = 0}$。 当${j=2}$时,能放下${w_0}$,于是有 ${f(0, 2)\ = \ v_0=6}$。 当${j=3}$时,也能放下${w_0}$,但我们只有一个物品0,因此它的值依然是6,于是一直到${j=10}$时,它的值都是${v_0}$。

wvi\j012345678910
26000666666666
231
652
543
464

根据第一行,我们得到如下方程

clipboard.png

当背包容量少于物品価积时,总价值为0,否则为物品的价值

然后我们看第二行,确定确定${f(1,0...10)}$这11个元素的值。当${j=0}$ 时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,0)=0}$。 当${j=1}$时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,1)=0}$. 当${j=2}$时,它可以选择放入物品1或不放。

如果选择不放物品1,背包里面有物品0,最大价值为6。

如果选择放入物品1,我们要用算出背包放入物品1后还有多少容量,然后根据容量查出它的价值,再加上物品1的价值,即${f(0,j-w_1)+v_1}$ 。由于我们的目标是尽可能装最值钱的物品, 因此放与不放, 我们需要通过比较来决定,于是有

clipboard.png

显然${v_1=2,v_0=6}$, 因此这里填${v_0}$。 当${j=3}$时, 情况相同。 当${j=4}$,能同时放下物品0与物品1,我们这个公式的计算结果也合乎我们的预期, 得到${f(1,4)=9}$。 当${j>4}$时, 由于背包只能放物品0与物品1,那么它的最大价值也一直停留在${v_0+v_1=9}$

wvi\j012345678910
26000666666666
23100669999999
652
543
464

我们再看第三行,当${j=0}$时,什么都放不下,${f(2,0)=0}$。当${j=1}$时,依然什么也放不下,${f(2,1)=0}$,当${j=2}$时,虽然放不下${w_2}$,但我们根据上表得知这个容号时,背包能装下的最大价值是6。继续计算下去,其实与上面推导的公式结果是一致的,说明公式是有效的。当${j=8}$时,背包可以是放物品0、1,或者放物品1、2,或者放物品0、2。物品0、1的价值,我们在表中就可以看到是9,至于其他两种情况我们姑且不顾,我们目测就知道是最优值是${6+5=11}$, 恰恰我们的公式也能正确计算出来。当${j=10}$时,刚好三个物品都能装下,它们的总值为14,即${f(2,10)=14}$

第三行的结果如下:

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543
464

整理一下第1,2行的适用方程:

clipboard.png

我们根据此方程,继续计算下面各列,于是得到

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

至此,我们就可以得到解为15.

我们最后根据0-1背包问题的最优子结构性质,建立计算${f(i,j)}$的递归式:

clipboard.png

//by 司徒正美
 function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        if(j < weights[0]){ //如果容量不能放下物品0的重量,那么价值为0
           f[0][j] = 0
        }else{ //否则等于物体0的价值
           f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
            }
        }
    }
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)

1.3 各种优化:

合并循环

现在方法里面有两个大循环,它们可以合并成一个。

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    for(var i = 0 ; i < n; i++){
        f[i] = []
    }
   for(var i = 0; i < n; i++ ){
       for(var j = 0; j <= W; j++){
            if(i === 0){ //第一行
                f[i][j] = j < weights[i] ? 0 : values[i]
            }else{
                if(j < weights[i]){ //等于之前的最优值
                    f[i][j] = f[i-1][j]
                }else{
                    f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
                }
            }
        }
    }
    return f[n-1][W]
}

然后我们再认真地思考一下,为什么要孤零零地专门处理第一行呢?f[i][j] = j < weights[i] ? 0 : values[i]是不是能适用于下面这一行f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 。Math.max可以轻松转换为三元表达式,结构极其相似。而看一下i-1的边界问题,有的书与博客为了解决它,会添加第0行,全部都是0,然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0>0}$的情况,方程与其他教科书的一模一样了!

clipboard.png

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = new Array(W).fill(0)
        for(var j=0; j<=W; j++){//注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3
            }
        }
    }
    return f[n-1][W]
}
wvi\j012345678910
XX-1000000000000
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

负一行的出现可以大大减少了在双层循环的分支判定。是一个很好的技巧。

注意,许多旧的教程与网上文章,通过设置二维数组的第一行为0来解决i-1的边界问题(比如下图)。当然也有一些思维转不过来的缘故,他们还在坚持数字以1开始,而我们新世代的IT人已经确立从0开始的编程思想。

image_1c3lm81p3gd09n5pjk1i4aif92d.png-110.2kB

选择物品

上面讲解了如何求得最大价值,现在我们看到底选择了哪些物品,这个在现实中更有意义。许多书与博客很少提到这一点,就算给出的代码也不对,估计是在设计状态矩阵就出错了。

仔细观察矩阵,从${f(n-1,W)}$逆着走向${f(0,0)}$,设i=n-1,j=W,如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品,因此我们只要当前行不等于上一行的总价值,就能挑出第i件物品,然后j减去该物品的重量,一直找到j = 0就行了。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    var selected = [];
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = [] //创建当前的二维数组
        for(var j=0; j<=W; j++){ //注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]//case 1
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2
            }
        }
    }
    var j = W, w = 0
    for(var i=n-1; i>=0; i--){
         if(f[i][j] > f[i-1][j]){
             selected.push(i)
             console.log("物品",i,"其重量为", weights[i],"其价格为", values[i])
             j = j - weights[i];
             w +=  weights[i]
         }
     }
    console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W])
    return [f[n-1][W], selected.reverse() ]
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k62d511dtgo7gud815q866m16.png-22.8kB
image_1c3k617gc6jp10pn1ean1lv81boqp.png-28.5kB

使用滚动数组压缩空间

所谓滚动数组,目的在于优化空间,因为目前我们是使用一个${i*j}$的二维数组来储存每一步的最优解。在求解的过程中,我们可以发现,当前状态只与前一行的状态有关,那么更之前存储的状态信息已经无用了,可以舍弃的,我们只需要存储当前状态和前一行状态,所以只需使用${2*j}$的空间,循环滚动使用,就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
    var lineA = new Array(W+1).fill(0)
    var lineB = [], lastLine = 0, currLine 
    var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行
        for(var j=0; j<=W; j++){
            f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[lastLine][j]
                var b = f[lastLine][j-weights[i]] + values[i]
                f[currLine][j] = Math.max(a, b);//case3
            }
           
        }
        lastLine = currLine//交换行
   }
   return f[currLine][W];
}

var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

我们还可以用更hack的方法代替currLine, lastLine

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
   
    var f = [new Array(W+1).fill(0),[]], now = 1, last //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        for(var j=0; j<=W; j++){
            f[now][j] = f[1-now][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[1-now][j]
                var b = f[1-now][j-weights[i]] + values[i]
                f[now][j] = Math.max(a, b);//case3
            }
         }
         last = f[now]
         now = 1-now // 1 - 0 => 1;1 - 1 => 0; 1 - 0 => 1 ....
   }
   return last[W];
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

注意,这种解法由于丢弃了之前N行的数据,因此很难解出挑选的物品,只能求最大价值。

使用一维数组压缩空间

观察我们的状态迁移方程:

clipboard.png

weights为每个物品的重量,values为每个物品的价值,W是背包的容量,i表示要放进第几个物品,j是背包现时的容量(假设我们的背包是魔术般的可放大,从0变到W)。

我们假令i = 0

clipboard.png

f中的-1就变成没有意义,因为没有第-1行,而weights[0], values[0]继续有效,${f(0,j)}$也有意义,因为我们全部放到一个一维数组中。于是:

clipboard.png

这方程后面多加了一个限制条件,要求是从大到小循环。为什么呢?

假设有物体${\cal z}$容量2,价值${v_z}$很大,背包容量为5,如果j的循环顺序不是逆序,那么外层循环跑到物体${\cal z}$时, 内循环在${j=2}$时 ,${\cal z}$被放入背包。当${j=4}$时,寻求最大价值,物体z放入背包,${f(4)=max(f(4),f(2)+v_z) }$, 这里毫无疑问后者最大。 但此时${f(2)+v_z}$中的${f(2)}$ 已经装入了一次${\cal z}$,这样一来${\cal z}$被装入两次不符合要求, 如果逆序循环j, 这一问题便解决了。

javascript实现:

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var j = W; j >= weights[i]; j--){  
            f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);
        }
        console.log(f.concat()) //调试
    }
    return f[W];
}
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k7lit11fkd1ufumfuovbidr1j.png-29.6kB

1.4 递归法解01背包

由于这不是动态规则的解法,大家多观察方程就理解了:

//by 司徒正美
function knapsack(n, W, weights, values, selected) {
    if (n == 0 || W == 0) {
        //当物品数量为0,或者背包容量为0时,最优解为0
        return 0;
    } else {
        //从当前所剩物品的最后一个物品开始向前,逐个判断是否要添加到背包中
        for (var i = n - 1; i >= 0; i--) {
            //如果当前要判断的物品重量大于背包当前所剩的容量,那么就不选择这个物品
            //在这种情况的最优解为f(n-1,C)
            if (weights[i] > W) {
                return knapsack(n - 1, W, weights, values, selected);
            } else {
                var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
                var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
                //返回选择物品i和不选择物品i中最优解大的一个
                if (a > b) {
                    selected[i] = 0; //这种情况下表示物品i未被选取
                    return a;
                } else {
                    selected[i] = 1; //物品i被选取
                    return b;
                }
            }
        }
    }
}        
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
    if(el){
        console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
    }
})

image_1c3kfq8nhddj12m11eh1r68189520.png-16.8kB

完全背包问题

2.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品没有上限,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

2.2 问题分析:

最简单思路就是把完全背包拆分成01背包,就是把01背包中状态转移方程进行扩展,也就是说01背包只考虑放与不放进去两种情况,而完全背包要考虑 放0、放1、放2...的情况,

clipboard.png

这个k当然不是无限的,它受背包的容量与单件物品的重量限制,即${j/weights[i]}$。假设我们只有1种商品,它的重量为20,背包的容量为60,那么它就应该放3个,在遍历时,就0、1、2、3地依次尝试。

程序需要求解${n*W}$个状态,每一个状态需要的时间为${O(W/w_i)}$,总的复杂度为${O(nW*Σ(W/w_i))}$。

我们再回顾01背包经典解法的核心代码

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))
      }
   }
}

现在多了一个k,就意味着多了一重循环

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       for(var k = 0; k < j / weights[i]; k++){
          f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))
        }
      }
   }
}

javascript的完整实现:

function completeKnapsack(weights, values, W){
    var f = [], n = weights.length;
    f[-1] = [] //初始化边界
    for(var i = 0; i <= W; i++){
        f[-1][i] = 0
    }
    for (var i = 0;i < n;i++){
        f[i] = new Array(W+1)
        for (var j = 0;j <= W;j++) {
            f[i][j] = 0;
            var bound = j / weights[i];
            for (var k = 0;k <= bound;k++) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return f[n-1][W];
}
//物品个数n = 3,背包容量为W = 5,则背包可以装下的最大价值为40.
var a = completeKnapsack([3,2,2],[5,10,20], 5) 
console.log(a) //40

2.3 O(nW)优化

我们再进行优化,改变一下f思路,让${f(i,j)}$表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。

所以说,对于第i件物品有放或不放两种情况,而放的情况里又分为放1件、2件、......${j/w_i}$件

如果不放, 那么${f(i,j)=f(i-1,j)}$;如果放,那么当前背包中应该出现至少一件第i种物品,所以f(i,j)中至少应该出现一件第i种物品,即${f(i,j)=f(i,j-w_i)+v_i}$,为什么会是${f(i,j-w_i)+v_i}$?

因为我们要把当前物品i放入包内,因为物品i可以无限使用,所以要用${f(i,j-w_i)}$;如果我们用的是${f(i-1,j-w_i)}$,${f(i-1,j-w_i)}$的意思是说,我们只有一件当前物品i,所以我们在放入物品i的时候需要考虑到第i-1个物品的价值${f(i-1,j-w_i)}$;但是现在我们有无限件当前物品i,我们不用再考虑第i-1个物品了,我们所要考虑的是在当前容量下是否再装入一个物品i,而${(j-w_i)}$的意思是指要确保${f(i,j)}$至少有一件第i件物品,所以要预留c(i)的空间来存放一件第i种物品。总而言之,如果放当前物品i的话,它的状态就是它自己"i",而不是上一个"i-1"。

所以说状态转移方程为:

clipboard.png

与01背包的相比,只是一点点不同,我们也不需要三重循环了

clipboard.png

javascript的完整实现:

function unboundedKnapsack(weights, values, W) {
    var f = [],
        n = weights.length;
    f[-1] = []; //初始化边界
    for (let i = 0; i <= W; i++) {
        f[-1][i] = 0;
    }
    for (let i = 0; i < n; i++) {
        f[i] = [];
        for (let j = 0; j <= W; j++) {
            if (j < weights[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - weights[i]] + values[i]);
            }
        }
        console.log(f[i].concat());//调试
    }
    return f[n - 1][W];
}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

我们可以继续优化此算法,可以用一维数组写

我们用${f(j)}$表示当前可用体积j的价值,我们可以得到和01背包一样的递推式:

clipboard.png

function unboundedKnapsack(weights, values, W) {
    var n = weights.length,
    f = new Array(W + 1).fill(0);
    for(var i=0; i< n; ++i){
        for(j = weights[i]; j <= W; ++j) {
          var tmp = f[j-weights[i]]+values[i];
          f[j] = (f[j] > tmp) ? f[j] : tmp;
        }
    }
    console.log(f)//调试
    return f[W];
}
var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

多重背包问题

3.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品最多有numbers[i]件可用,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

3.2 问题分析:

多重背包就是一个进化版完全背包。在我们做完全背包的第一个版本中,就是将它转换成01背包,然后限制k的循环

直接套用01背包的一维数组解法

function knapsack(weights, values, numbers,  W){
    var n = weights.length;
    var f= new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var k=0; k<numbers[i]; k++)//其实就是把这类物品展开,调用numbers[i]次01背包代码  
         for(var j=W; j>=weights[i]; j--)//正常的01背包代码  
             f[j]=Math.max(f[j],f[j-weights[i]]+values[i]);  
    }
    return f[W];
}
var b = knapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b)

3.3 使用二进制优化

其实说白了我们最朴素的多重背包做法是将有数量限制的相同物品看成多个不同的0-1背包。这样的时间复杂度为${O(W*Σn(i))}$, W为空间容量 ,n(i)为每种背包的数量限制。如果这样会超时,我们就得考虑更优的拆分方法,由于拆成1太多了,我们考虑拆成二进制数,对于13的数量,我们拆成1,2,4,6(有个6是为了凑数)。 19 我们拆成1,2,4,8,4 (最后的4也是为了凑和为19)。经过这个样的拆分我们可以组合出任意的小于等于n(i)的数目(二进制啊,必然可以)。j极大程度缩减了等效为0-1背包时候的数量。 大概可以使时间复杂度缩减为${O(W*log(ΣN(i))}$;

定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

证明如下:

(1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

(2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

(3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

(证毕!)

function mKnapsack(weights, values, numbers, W) {
    var kind = 0; //新的物品种类
    var ws = []; //新的物品重量
    var vs = []; //新的物品价值
    var n = weights.length;
    /**
     * 二进制分解
     * 100=1+2+4+8+16+32+37,观察可以得出100以内任何一个数都可以由以上7个数选择组合得到,
     * 所以对物品数目就不是从0都100遍历,而是0,1,2,4,8,16,32,37遍历,时间大大优化。
     */
    for (let i = 0; i < n; i++) {
        var w = weights[i];
        var v = values[i];
        var num = numbers[i];
        for (let j = 1; ; j *= 2) {
            if (num >= j) {
                ws[kind] = j * w;
                vs[kind] = j * v;
                num -= j;
                kind++;
            } else {
                ws[kind] = num * w;
                vs[kind] = num * v;
                kind++;
                break;
            }
        }
    }
    //01背包解法
    var f = new Array(W + 1).fill(0);
    for (let i = 0; i < kind; i++) {
        for (let j = W; j >= ws[i]; j--) {
            f[j] = Math.max(f[j], f[j - ws[i]] + vs[i]);
        }
    }
    return f[W];
}

var b = mKnapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b) //9

参考链接

查看原文

xgqfrms 赞了文章 · 2020-10-12

javascript背包问题详解

image_1c3ds1q091ubg5bm1gaj3vv1jm19.png-64.6kB

引子

打算好好学一下算法,先拿背包问题入手。但是网上许多教程都是C++或java或python,大部分作者都是在校生,虽然算法很强,但是完全没有工程意识,全局变量满天飞,变量名不明所以。我查了许多资料,花了一个星期才搞懂,最开始的01背包耗时最多,以前只会枚举(就是普通的for循环,暴力地一步步遍历下去),递归与二分,而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

01背包问题

篇幅可能有点长,但请耐心看一下,你会觉得物有所值的。本文以后还会扩展,因为我还没有想到完全背包与多重背包打印物品编号的方法。如果有高人知道,劳烦在评论区指教一下。

注意,由于社区不支持LaTex数学公式,你们看到${xxxx}$,就自己将它们过滤吧。

1.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品均只有一件,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

对于一种物品,要么装入背包,要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为01背包问题

1.2 问题分析:

数据:物品个数${n=5}$,物品重量${weights=[2,2,6,5,4]}$,物品价值${values=[6,3,5,4,6]}$,背包总容量${W=10}$。

我们设置一个矩阵${f}$来记录结果,${f(i, j)}$ 表示可选物品为 ${i...n}$ 背包容量为 ${j(0<=j<=W)}$ 时, 背包中所放物品的最大价值。

wvi\j012345678910
260
231
652
543
464

我们先看第一行,物品0的体积为2,价值为6,当容量为0时,什么也放不下,因此第一个格式只能填0,程序表示为${f(0,0) = 0}$或者${f[0][0] = 0}$。 当${j=1}$时,依然放不下${w_0}$,因此依然为0,${f(0, 1) = 0}$。 当${j=2}$时,能放下${w_0}$,于是有 ${f(0, 2)\ = \ v_0=6}$。 当${j=3}$时,也能放下${w_0}$,但我们只有一个物品0,因此它的值依然是6,于是一直到${j=10}$时,它的值都是${v_0}$。

wvi\j012345678910
26000666666666
231
652
543
464

根据第一行,我们得到如下方程

clipboard.png

当背包容量少于物品価积时,总价值为0,否则为物品的价值

然后我们看第二行,确定确定${f(1,0...10)}$这11个元素的值。当${j=0}$ 时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,0)=0}$。 当${j=1}$时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,1)=0}$. 当${j=2}$时,它可以选择放入物品1或不放。

如果选择不放物品1,背包里面有物品0,最大价值为6。

如果选择放入物品1,我们要用算出背包放入物品1后还有多少容量,然后根据容量查出它的价值,再加上物品1的价值,即${f(0,j-w_1)+v_1}$ 。由于我们的目标是尽可能装最值钱的物品, 因此放与不放, 我们需要通过比较来决定,于是有

clipboard.png

显然${v_1=2,v_0=6}$, 因此这里填${v_0}$。 当${j=3}$时, 情况相同。 当${j=4}$,能同时放下物品0与物品1,我们这个公式的计算结果也合乎我们的预期, 得到${f(1,4)=9}$。 当${j>4}$时, 由于背包只能放物品0与物品1,那么它的最大价值也一直停留在${v_0+v_1=9}$

wvi\j012345678910
26000666666666
23100669999999
652
543
464

我们再看第三行,当${j=0}$时,什么都放不下,${f(2,0)=0}$。当${j=1}$时,依然什么也放不下,${f(2,1)=0}$,当${j=2}$时,虽然放不下${w_2}$,但我们根据上表得知这个容号时,背包能装下的最大价值是6。继续计算下去,其实与上面推导的公式结果是一致的,说明公式是有效的。当${j=8}$时,背包可以是放物品0、1,或者放物品1、2,或者放物品0、2。物品0、1的价值,我们在表中就可以看到是9,至于其他两种情况我们姑且不顾,我们目测就知道是最优值是${6+5=11}$, 恰恰我们的公式也能正确计算出来。当${j=10}$时,刚好三个物品都能装下,它们的总值为14,即${f(2,10)=14}$

第三行的结果如下:

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543
464

整理一下第1,2行的适用方程:

clipboard.png

我们根据此方程,继续计算下面各列,于是得到

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

至此,我们就可以得到解为15.

我们最后根据0-1背包问题的最优子结构性质,建立计算${f(i,j)}$的递归式:

clipboard.png

//by 司徒正美
 function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        if(j < weights[0]){ //如果容量不能放下物品0的重量,那么价值为0
           f[0][j] = 0
        }else{ //否则等于物体0的价值
           f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
            }
        }
    }
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)

1.3 各种优化:

合并循环

现在方法里面有两个大循环,它们可以合并成一个。

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    for(var i = 0 ; i < n; i++){
        f[i] = []
    }
   for(var i = 0; i < n; i++ ){
       for(var j = 0; j <= W; j++){
            if(i === 0){ //第一行
                f[i][j] = j < weights[i] ? 0 : values[i]
            }else{
                if(j < weights[i]){ //等于之前的最优值
                    f[i][j] = f[i-1][j]
                }else{
                    f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
                }
            }
        }
    }
    return f[n-1][W]
}

然后我们再认真地思考一下,为什么要孤零零地专门处理第一行呢?f[i][j] = j < weights[i] ? 0 : values[i]是不是能适用于下面这一行f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 。Math.max可以轻松转换为三元表达式,结构极其相似。而看一下i-1的边界问题,有的书与博客为了解决它,会添加第0行,全部都是0,然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0>0}$的情况,方程与其他教科书的一模一样了!

clipboard.png

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = new Array(W).fill(0)
        for(var j=0; j<=W; j++){//注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3
            }
        }
    }
    return f[n-1][W]
}
wvi\j012345678910
XX-1000000000000
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

负一行的出现可以大大减少了在双层循环的分支判定。是一个很好的技巧。

注意,许多旧的教程与网上文章,通过设置二维数组的第一行为0来解决i-1的边界问题(比如下图)。当然也有一些思维转不过来的缘故,他们还在坚持数字以1开始,而我们新世代的IT人已经确立从0开始的编程思想。

image_1c3lm81p3gd09n5pjk1i4aif92d.png-110.2kB

选择物品

上面讲解了如何求得最大价值,现在我们看到底选择了哪些物品,这个在现实中更有意义。许多书与博客很少提到这一点,就算给出的代码也不对,估计是在设计状态矩阵就出错了。

仔细观察矩阵,从${f(n-1,W)}$逆着走向${f(0,0)}$,设i=n-1,j=W,如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品,因此我们只要当前行不等于上一行的总价值,就能挑出第i件物品,然后j减去该物品的重量,一直找到j = 0就行了。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    var selected = [];
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = [] //创建当前的二维数组
        for(var j=0; j<=W; j++){ //注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]//case 1
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2
            }
        }
    }
    var j = W, w = 0
    for(var i=n-1; i>=0; i--){
         if(f[i][j] > f[i-1][j]){
             selected.push(i)
             console.log("物品",i,"其重量为", weights[i],"其价格为", values[i])
             j = j - weights[i];
             w +=  weights[i]
         }
     }
    console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W])
    return [f[n-1][W], selected.reverse() ]
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k62d511dtgo7gud815q866m16.png-22.8kB
image_1c3k617gc6jp10pn1ean1lv81boqp.png-28.5kB

使用滚动数组压缩空间

所谓滚动数组,目的在于优化空间,因为目前我们是使用一个${i*j}$的二维数组来储存每一步的最优解。在求解的过程中,我们可以发现,当前状态只与前一行的状态有关,那么更之前存储的状态信息已经无用了,可以舍弃的,我们只需要存储当前状态和前一行状态,所以只需使用${2*j}$的空间,循环滚动使用,就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
    var lineA = new Array(W+1).fill(0)
    var lineB = [], lastLine = 0, currLine 
    var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行
        for(var j=0; j<=W; j++){
            f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[lastLine][j]
                var b = f[lastLine][j-weights[i]] + values[i]
                f[currLine][j] = Math.max(a, b);//case3
            }
           
        }
        lastLine = currLine//交换行
   }
   return f[currLine][W];
}

var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

我们还可以用更hack的方法代替currLine, lastLine

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
   
    var f = [new Array(W+1).fill(0),[]], now = 1, last //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        for(var j=0; j<=W; j++){
            f[now][j] = f[1-now][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[1-now][j]
                var b = f[1-now][j-weights[i]] + values[i]
                f[now][j] = Math.max(a, b);//case3
            }
         }
         last = f[now]
         now = 1-now // 1 - 0 => 1;1 - 1 => 0; 1 - 0 => 1 ....
   }
   return last[W];
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

注意,这种解法由于丢弃了之前N行的数据,因此很难解出挑选的物品,只能求最大价值。

使用一维数组压缩空间

观察我们的状态迁移方程:

clipboard.png

weights为每个物品的重量,values为每个物品的价值,W是背包的容量,i表示要放进第几个物品,j是背包现时的容量(假设我们的背包是魔术般的可放大,从0变到W)。

我们假令i = 0

clipboard.png

f中的-1就变成没有意义,因为没有第-1行,而weights[0], values[0]继续有效,${f(0,j)}$也有意义,因为我们全部放到一个一维数组中。于是:

clipboard.png

这方程后面多加了一个限制条件,要求是从大到小循环。为什么呢?

假设有物体${\cal z}$容量2,价值${v_z}$很大,背包容量为5,如果j的循环顺序不是逆序,那么外层循环跑到物体${\cal z}$时, 内循环在${j=2}$时 ,${\cal z}$被放入背包。当${j=4}$时,寻求最大价值,物体z放入背包,${f(4)=max(f(4),f(2)+v_z) }$, 这里毫无疑问后者最大。 但此时${f(2)+v_z}$中的${f(2)}$ 已经装入了一次${\cal z}$,这样一来${\cal z}$被装入两次不符合要求, 如果逆序循环j, 这一问题便解决了。

javascript实现:

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var j = W; j >= weights[i]; j--){  
            f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);
        }
        console.log(f.concat()) //调试
    }
    return f[W];
}
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k7lit11fkd1ufumfuovbidr1j.png-29.6kB

1.4 递归法解01背包

由于这不是动态规则的解法,大家多观察方程就理解了:

//by 司徒正美
function knapsack(n, W, weights, values, selected) {
    if (n == 0 || W == 0) {
        //当物品数量为0,或者背包容量为0时,最优解为0
        return 0;
    } else {
        //从当前所剩物品的最后一个物品开始向前,逐个判断是否要添加到背包中
        for (var i = n - 1; i >= 0; i--) {
            //如果当前要判断的物品重量大于背包当前所剩的容量,那么就不选择这个物品
            //在这种情况的最优解为f(n-1,C)
            if (weights[i] > W) {
                return knapsack(n - 1, W, weights, values, selected);
            } else {
                var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
                var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
                //返回选择物品i和不选择物品i中最优解大的一个
                if (a > b) {
                    selected[i] = 0; //这种情况下表示物品i未被选取
                    return a;
                } else {
                    selected[i] = 1; //物品i被选取
                    return b;
                }
            }
        }
    }
}        
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
    if(el){
        console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
    }
})

image_1c3kfq8nhddj12m11eh1r68189520.png-16.8kB

完全背包问题

2.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品没有上限,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

2.2 问题分析:

最简单思路就是把完全背包拆分成01背包,就是把01背包中状态转移方程进行扩展,也就是说01背包只考虑放与不放进去两种情况,而完全背包要考虑 放0、放1、放2...的情况,

clipboard.png

这个k当然不是无限的,它受背包的容量与单件物品的重量限制,即${j/weights[i]}$。假设我们只有1种商品,它的重量为20,背包的容量为60,那么它就应该放3个,在遍历时,就0、1、2、3地依次尝试。

程序需要求解${n*W}$个状态,每一个状态需要的时间为${O(W/w_i)}$,总的复杂度为${O(nW*Σ(W/w_i))}$。

我们再回顾01背包经典解法的核心代码

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))
      }
   }
}

现在多了一个k,就意味着多了一重循环

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       for(var k = 0; k < j / weights[i]; k++){
          f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))
        }
      }
   }
}

javascript的完整实现:

function completeKnapsack(weights, values, W){
    var f = [], n = weights.length;
    f[-1] = [] //初始化边界
    for(var i = 0; i <= W; i++){
        f[-1][i] = 0
    }
    for (var i = 0;i < n;i++){
        f[i] = new Array(W+1)
        for (var j = 0;j <= W;j++) {
            f[i][j] = 0;
            var bound = j / weights[i];
            for (var k = 0;k <= bound;k++) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return f[n-1][W];
}
//物品个数n = 3,背包容量为W = 5,则背包可以装下的最大价值为40.
var a = completeKnapsack([3,2,2],[5,10,20], 5) 
console.log(a) //40

2.3 O(nW)优化

我们再进行优化,改变一下f思路,让${f(i,j)}$表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。

所以说,对于第i件物品有放或不放两种情况,而放的情况里又分为放1件、2件、......${j/w_i}$件

如果不放, 那么${f(i,j)=f(i-1,j)}$;如果放,那么当前背包中应该出现至少一件第i种物品,所以f(i,j)中至少应该出现一件第i种物品,即${f(i,j)=f(i,j-w_i)+v_i}$,为什么会是${f(i,j-w_i)+v_i}$?

因为我们要把当前物品i放入包内,因为物品i可以无限使用,所以要用${f(i,j-w_i)}$;如果我们用的是${f(i-1,j-w_i)}$,${f(i-1,j-w_i)}$的意思是说,我们只有一件当前物品i,所以我们在放入物品i的时候需要考虑到第i-1个物品的价值${f(i-1,j-w_i)}$;但是现在我们有无限件当前物品i,我们不用再考虑第i-1个物品了,我们所要考虑的是在当前容量下是否再装入一个物品i,而${(j-w_i)}$的意思是指要确保${f(i,j)}$至少有一件第i件物品,所以要预留c(i)的空间来存放一件第i种物品。总而言之,如果放当前物品i的话,它的状态就是它自己"i",而不是上一个"i-1"。

所以说状态转移方程为:

clipboard.png

与01背包的相比,只是一点点不同,我们也不需要三重循环了

clipboard.png

javascript的完整实现:

function unboundedKnapsack(weights, values, W) {
    var f = [],
        n = weights.length;
    f[-1] = []; //初始化边界
    for (let i = 0; i <= W; i++) {
        f[-1][i] = 0;
    }
    for (let i = 0; i < n; i++) {
        f[i] = [];
        for (let j = 0; j <= W; j++) {
            if (j < weights[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - weights[i]] + values[i]);
            }
        }
        console.log(f[i].concat());//调试
    }
    return f[n - 1][W];
}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

我们可以继续优化此算法,可以用一维数组写

我们用${f(j)}$表示当前可用体积j的价值,我们可以得到和01背包一样的递推式:

clipboard.png

function unboundedKnapsack(weights, values, W) {
    var n = weights.length,
    f = new Array(W + 1).fill(0);
    for(var i=0; i< n; ++i){
        for(j = weights[i]; j <= W; ++j) {
          var tmp = f[j-weights[i]]+values[i];
          f[j] = (f[j] > tmp) ? f[j] : tmp;
        }
    }
    console.log(f)//调试
    return f[W];
}
var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

多重背包问题

3.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品最多有numbers[i]件可用,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

3.2 问题分析:

多重背包就是一个进化版完全背包。在我们做完全背包的第一个版本中,就是将它转换成01背包,然后限制k的循环

直接套用01背包的一维数组解法

function knapsack(weights, values, numbers,  W){
    var n = weights.length;
    var f= new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var k=0; k<numbers[i]; k++)//其实就是把这类物品展开,调用numbers[i]次01背包代码  
         for(var j=W; j>=weights[i]; j--)//正常的01背包代码  
             f[j]=Math.max(f[j],f[j-weights[i]]+values[i]);  
    }
    return f[W];
}
var b = knapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b)

3.3 使用二进制优化

其实说白了我们最朴素的多重背包做法是将有数量限制的相同物品看成多个不同的0-1背包。这样的时间复杂度为${O(W*Σn(i))}$, W为空间容量 ,n(i)为每种背包的数量限制。如果这样会超时,我们就得考虑更优的拆分方法,由于拆成1太多了,我们考虑拆成二进制数,对于13的数量,我们拆成1,2,4,6(有个6是为了凑数)。 19 我们拆成1,2,4,8,4 (最后的4也是为了凑和为19)。经过这个样的拆分我们可以组合出任意的小于等于n(i)的数目(二进制啊,必然可以)。j极大程度缩减了等效为0-1背包时候的数量。 大概可以使时间复杂度缩减为${O(W*log(ΣN(i))}$;

定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

证明如下:

(1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

(2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

(3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

(证毕!)

function mKnapsack(weights, values, numbers, W) {
    var kind = 0; //新的物品种类
    var ws = []; //新的物品重量
    var vs = []; //新的物品价值
    var n = weights.length;
    /**
     * 二进制分解
     * 100=1+2+4+8+16+32+37,观察可以得出100以内任何一个数都可以由以上7个数选择组合得到,
     * 所以对物品数目就不是从0都100遍历,而是0,1,2,4,8,16,32,37遍历,时间大大优化。
     */
    for (let i = 0; i < n; i++) {
        var w = weights[i];
        var v = values[i];
        var num = numbers[i];
        for (let j = 1; ; j *= 2) {
            if (num >= j) {
                ws[kind] = j * w;
                vs[kind] = j * v;
                num -= j;
                kind++;
            } else {
                ws[kind] = num * w;
                vs[kind] = num * v;
                kind++;
                break;
            }
        }
    }
    //01背包解法
    var f = new Array(W + 1).fill(0);
    for (let i = 0; i < kind; i++) {
        for (let j = W; j >= ws[i]; j--) {
            f[j] = Math.max(f[j], f[j - ws[i]] + vs[i]);
        }
    }
    return f[W];
}

var b = mKnapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b) //9

参考链接

查看原文

赞 87 收藏 137 评论 9

xgqfrms 关注了专栏 · 2020-09-10

微醺岁月

暂无

关注 40

xgqfrms 收藏了文章 · 2020-09-10

一行代码实现一个简单的模板字符串替换

起始

同许多初学 Javascript 的菜鸟一样,起初,我也是采用拼接字符串的形式,将 JSON 数据嵌入 HTML 中。开始时代码量较少,暂时还可以接受。但当页面结构复杂起来后,其弱点开始变得无法忍受起来:

  • 书写不连贯。每写一个变量就要断一下,插入一个 + 和 "。十分容易出错。
  • 无法重用。HTML 片段都是离散化的数据,难以对其中重复的部分进行提取。
  • 无法很好地利用 <template> 标签。这是 HTML5 中新增的一个标签,标准极力推荐将 HTML 模板放入 <template> 标签中,使代码更简洁。

当时我的心情就是这样的:
这TMD是在逗我吗。

于是出来了后来的 ES6ES6的模板字符串用起来着实方便,对于比较老的项目,项目没webpackgulp 等构建工具,无法使用 ES6 的语法,但是想也借鉴这种优秀的处理字符串拼接的方式,我们不妨可以试着自己写一个,主要是思路,可以使用 ES6 语法模拟 ES6的模板字符串的这个功能。

后端返回的一般都是 JSON 的数据格式,所以我们按照下面的规则进行模拟。

需求描述

实现一个 render(template, context) 方法,将 template 中的占位符用 context 填充。

要求:

不需要有控制流成分(如 循环、条件 等等),只要有变量替换功能即可
级联的变量也可以展开
被转义的的分隔符 { 和 } 不应该被渲染,分隔符与变量之间允许有空白字符
var obj = {name:"二月",age:"15"};
var str = "{{name}}很厉害,才{{age}}岁";
输出:二月很厉害,才15岁。

PS:本文需要对正则表达式有一定的了解,如果还不了解正则表达式,建议先去学习一下,正则也是面试笔试必备的技能,上面链接末尾有不少正则学习的链接。

如果是你,你会怎么实现?可以先尝试自己写写,实现也不难。

先不说我的实现,我把这个题给其他好友做的时候,实现的不尽相同,我们先看几位童鞋的实现,然后在他们的基础上找到常见的误区以及实现不够优雅的地方。

二月童鞋:

let str = "{{name}}很厉害,才{{age}}岁"
let obj = {name: '二月', age: 15}
function test(str, obj){
    let _s = str.replace(/\{\{(\w+)\}\}/g, '$1')
    let result
    for(let k in obj) {
      _s = _s.replace(new RegExp(k, 'g'), obj[k])
    }
  return _s
}
const s = test(str, obj)

最基本的是实现了,但是代码还是有很多问题没考虑到,首先 Object 的 key 值不一定只是 w,
还有就是如果字符串是这种的:

let str = "{{name}}很name厉害,才{{age}}岁"`
会输出 :二月很厉害二月害,才15岁

此处你需要了解正则的分组才会明白 $1 的含义,错误很明显,把本来就是字符串不要替换的 name 也给替换了,从代码我们可以看出二月的思路。

  1. 代码的作用目标是 str,先用正则匹配出 {{name}}{{age}},然后用分组获取括号的 name,age,最后用 replace 方法把 {{name}}{{age}} 替换成 nameage,最后字符串就成了 name很name厉害,才age岁,最后 for in 循环的时候才导致一起都被替换掉了。
  2. for in 循环完全没必要,能不用 for in 尽量不要用 for infor in 会遍历自身以及原型链所有的属性。

志钦童鞋:

var str = "{{name}}很厉害,才{{age}}岁";
var str2 = "{{name}}很厉name害,才{{age}}岁{{name}}";

var obj = {name: '周杰伦', age: 15};
function fun(str, obj) {
    var arr;
    arr = str.match(/{{[a-zA-Z\d]+}}/g);
    for(var i=0;i<arr.length;i++){
        arr[i] = arr[i].replace(/{{|}}/g,'');
        str = str.replace('{{'+arr[i]+'}}',obj[arr[i]]);
    }
    return str;
}
console.log(fun(str,obj));
console.log(fun(str2,obj));

思路是正确的,知道最后要替换的是 {{name}}{{age}} 整体,而不是像二月童鞋那样最后去替换 name,所有跑起来肯定没问题,实现是实现了但是感觉有点那个,我们要探讨的是一行代码也就是代码越少越好。

小维童鞋:

function a(str, obj) {
  var str1 = str;
  for (var key in obj) {
    var re = new RegExp("{{" + key + "}}", "g");
    str1 = str1.replace(re, obj[key]);
  }
  console.log(str1);
}
const str = "{{name}}很厉name害{{name}},才{{age}}岁";
const obj = { name: "jawil", age: "15" };
a(str, obj);

实现的已经简单明了了,就是把 objkey 值遍历,然后拼成 {{key}},最后用 obj[key] 也就是 value{{key}} 整个给替换了,思路很好,跟我最初的版本一个样。

我的实现:

function parseString(str, obj) {
  Object.keys(obj).forEach(key => {
    str = str.replace(new RegExp(`{{${key}}}`,'g'), obj[key]);
  });
  return str;
}
const str = "{{name}}很厉name害{{name}},才{{age}}岁";
const obj = { name: "jawil", age: "15" };
console.log(parseString(str, obj));

其实这里还是有些问题的,首先我没用 for...in 循环就是为了考虑不必要的循环,因为 for...in 循环会遍历原型链所有的可枚举属性,造成不必要的循环。

我们可以简单看一个例子,看看 for...in的可怕性。

// Chrome v63
const div = document.createElement('div');
let m = 0;
for (let k in div) {
  m++;
}
let n = 0;
console.log(m); // 231
console.log(Object.keys(div).length); // 0

一个 DOM 节点属性竟然有这么多的属性,列举这个例子只是让大家看到 for in 遍历的效率问题,不要轻易用 for in循环,通过这个 DOM 节点之多也可以一定程度了解到 React Virtual DOM 的思想和优越性。

除了用 for in 循环获取 objkey 值,还可以用 Object.key() 获取,Object.getOwnPropertyNames() 以及 Reflect.ownKeys()也可以获取,那么这几种有啥区别呢?这里就简单说一下他们的一些区别。

for...in循环:会遍历对象自身的属性,以及原型属性,for...in 循环只遍历可枚举(不包括 enumerablefalse )属性。像 ArrayObject 使用内置构造函数所创建的对象都会继承自 Object.prototypeString.prototype 的不可枚举属性;

Object.key():可以得到自身可枚举的属性,但得不到原型链上的属性;

Object.getOwnPropertyNames():可以得到自身所有的属性(包括不可枚举),但得不到原型链上的属性, Symbols 属性也得不到.

Reflect.ownKeys:该方法用于返回对象的所有属性,基本等同于 Object.getOwnPropertyNames()Object.getOwnPropertySymbols 之和。

上面说的可能比较抽象,不够直观。可以看个我写的 DEMO,一切简单明鸟。

const parent = {
  a: 1,
  b: 2,
  c: 3
};
const child = {
  d: 4,
  e: 5,
  [Symbol()]: 6
};
child.__proto__ = parent;
Object.defineProperty(child, "d", { enumerable: false });

for (var attr in child) {
  console.log("for...in:", attr);// a,b,c,e
}
console.log("Object.keys:", Object.keys(child));// [ 'e' ]
console.log("Object.getOwnPropertyNames:", Object.getOwnPropertyNames(child)); // [ 'd', 'e' ]
console.log("Reflect.ownKeys:", Reflect.ownKeys(child)); //  [ 'd', 'e', Symbol() ]

最后实现

上面的实现其实已经很简洁了,但是还是有些不完美的地方,通过 MDN 首先我们先了解一下 replace 的用法。

通过文档里面写的 str.replace(regexp|substr, newSubStr|function) ,我们可以发现 replace 方法可以传入 function 回调函数,

function (replacement) 一个用来创建新子字符串的函数,该函数的返回值将替换掉第一个参数匹配到的结果。参考这个指定一个函数作为参数

有了这句话,其实就很好实现了,先看看具体代码再做下一步分析。

function render(template, context) {
  return template.replace(/\{\{(.*?)\}\}/g, (match, key) => context[key]);
}
const template = "{{name}}很厉name害,才{{age}}岁";
const context = { name: "jawil", age: "15" };
console.log(render(template, context));

可以对照上面文档的话来做分析:该函数的返回值(obj[key]=jawil)将替换掉第一个参数(match=={{name}})匹配到的结果。

简单分析一下:.*? 是正则固定搭配用法,表示非贪婪匹配模式,尽可能匹配少的,什么意思呢?举个简单的例子。

先看一个例子:

源字符串:aa<div>test1</div>bb<div>test2</div>cc

正则表达式一:<div>.*</div>

匹配结果一:<div>test1</div>bb<div>test2</div>

正则表达式二:<div>.*?</div>

匹配结果二:<div>test1</div>(这里指的是一次匹配结果,不使用/g,所以没包括<div>test2</div>)

根据上面的例子,从匹配行为上分析一下,什是贪婪与非贪婪匹配模式。

利用非贪婪匹配模就能匹配到所有的{{name}}{{age}},上面的也说到过正则分组,分组匹配到的就是 name,也就是 function 的第二个参数 key

所以这行代码的意思就很清楚,正则匹配到{{name}},分组获取 name,然后把 {{name}} 替换成 obj[name](jawil)

当然后来发现还有一个小问题,如果有空格的话就会匹配失败,类似这种写法:

const template = "{{name   }}很厉name害,才{{age   }}岁";

所以在上面的基础上还要去掉空格,其实也很简单,用正则或者 String.prototype.trim() 方法都行。

function render(template, context) {
  return template.replace(/\{\{(.*?)\}\}/g, (match, key) => context[key.trim()]);
}
const template = "{{name   }}很厉name害,才{{age   }}岁";
const context = { name: "jawil", age: "15" };
console.log(render(template, context));

将函数挂到 String 的原型链,得到最终版本

甚至,我们可以通过修改原型链,实现一些很酷的效果:

String.prototype.render = function (context) {
  return this.replace(/\{\{(.*?)\}\}/g, (match, key) => context[key.trim()]);
};

如果{}中间不是数字,则{}本身不需要转义,所以最终最简洁的代码:

String.prototype.render = function (context) {
  return this.replace(/{{(.*?)}}/g, (match, key) => context[key.trim()]);
};

之后,我们便可以这样调用啦:

"{{name}}很厉name害,才{{ age  }}岁".render({ name: "jawil", age: "15" });

收获

通过一个小小的模板字符串的实现,领悟到要把一个功能实现不难,要把做到完美真是难上加难,需要对基础掌握牢固,有一定的沉淀,然后不断地打磨才能比较优雅的实现,通过由一个很小的点往往可以拓展出很多的知识点。

一张图快速入门正则表达式:

查看原文

xgqfrms 回答了问题 · 2020-04-27

解决node.js 如何处理一个很大的文件

node.js 如何处理一个很大的文件

https://cnodejs.org/topic/55a...

使用fs.createReadStream()创建一个读文件流,这种方式可不受限于文件的大小;

https://juejin.im/post/5d3c27...

Buffer对象

https://www.jianshu.com/p/271...

JSONStream

https://github.com/dominictar...

https://sanster.xyz/2017/01/0...

http://stackoverflow.com/ques...

Buffer
Stream

https://zhuanlan.zhihu.com/p/...

https://www.cnblogs.com/tugen...

关注 2 回答 1

xgqfrms 关注了问题 · 2020-04-27

解决node.js 如何处理一个很大的文件

node.js 如何处理一个很大的文件

思路

arraybuffer

数据分段

时间分片

多线程

web workers

sevice workers

关注 2 回答 1

xgqfrms 提出了问题 · 2020-04-27

解决node.js 如何处理一个很大的文件

node.js 如何处理一个很大的文件

思路

arraybuffer

数据分段

时间分片

多线程

web workers

sevice workers

关注 2 回答 1

认证与成就

  • 获得 6 次点赞
  • 获得 7 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 7 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

  • gitbook for test

    100,000,000,000,000,000,000,000,000,000,000,000,000 It's veryveryvery hard for your spider!

注册于 2014-12-08
个人主页被 788 人浏览