背包问题记忆化函数实现！！（JavaScript可视化页面展示！）_记忆函数背包问题

背包问题（动态规划）

1.问题描述

给定n个重量为w1，….wn、价值为v1,……,vn的物品和一个承重量为W的背包，

求这些物品中最有价值的一个子集，并且要能够装到背包中

2.算法分析

在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

• 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
• 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。

3.关键代码

3.1使用的编程语言及程序使用说明

本算法演示采用JavaScript实现逻辑和HTML、CSS可视化显示。

打开iteml1.html的文件（使用浏览器，推荐chorme）如图所示：

3.2关键代码

//背包问题记忆化
MFKnapsack:function(i,j){
    var value = 0;
    if(this.F[i][j] < 0){
        if (j < parseInt(this.pws[i])){//如果添加的物品比当前背包重量还大，舍弃该物品
            value = this.MFKnapsack(i-1,j)
        }else{//这里递归使用核心的公式
            value = this.max(this.MFKnapsack(i-1,j),parseInt(this.pvs[i])+this.MFKnapsack(i-1,j-parseInt(this.pws[i])))
        }
        this.F[i][j] = value;
    }
    return this.F[i][j];
},
1
2
3
4
5
6
7
8
9
10
11
12
13

//背包问题主函数
backpackmain:function(){
    //pws和pvs首端添加0，因为背包的记忆功能算法使用的是Weights[1..n]和Valuess[1..n]
    this.pws.splice(0,0,0);
    this.pvs.splice(0,0,0);
    this.idxs.splice(0,0,0)
    this.F = new Array(this.pws.length);
    //初始化值
    for (var i = 0; i < this.pws.length; i++) {
        this.F[i] = new Array(parseInt(this.backpackweight)+1)
        for (var j = 0; j <= parseInt(this.backpackweight); j++) {
            if(i==0 || j==0){
                this.F[i][j] = 0;//对于非0行0列置0
            }else{
                this.F[i][j] = -1;//首行首列置1
            }
        }
    }
    this.MFKnapsack(this.pws.length-1,parseInt(this.backpackweight))
    //输出最优子集
    this.things = new Array();
    var j = parseInt(this.backpackweight);
    for (var i = this.pws.length-1; i > 0; i--) {
        if(this.F[i][j] == this.F[i-1][j]){
            while(this.F[i][j] == this.F[i-1][j]){
                i--;//从当前值往上一格找，如果上一个值和当前格值相等的话就不用该物品
            }
        }
        this.ts.push("物品"+i+",")//添加物品到最优解数组
        j = j - this.pws[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

4.效果验证

可得背包问题的矩阵：

可以从课本处验证此例子：

项目地址（欢迎白嫖！）：

https://github.com/DuoRouLongShu/AlgorithmItems.git