实验五回溯算法

实验目的

掌握回溯法算法的设计与分析步骤以及算法的具体实现。

实验要求

实验时间：2学时，对于给定的问题描述，生成实验报告。

实验内容

问题描述：有 $n$ 种物品，每种物品只有 $1$ 个。第 $i$ 种物品价值为 $v_i$，重量为 $w_i$，$i = 1, 2, \dots, n$。问如何选择放入背包的物品，使得总重量不超过 $B$，而价值达到最大？

使用回溯算法解决问题，给出分析过程。
给出算法的具体实现过程（源码及其详细注释）
给出算法的运行结果。

思路

在我看来，回溯法有另一个名字：及时止损的遍历法。
对于此问题，0-1 背包。每种物品只有选与不选的选项。由此构造一棵 $n$ 层二叉树，左为1，右为0，分别代表选与不选。

具体些

我们搜索一棵树，从左子树开始（意味着选择此物品），直到不能够继续装下，丢弃该节点的左子树后，向右搜索，直到叶子结点。然后比较当前的值与最大值，如果符合最优条件，那么记录此最优解，然后回溯。如果不符合，那么也回溯。

如何回溯

函数回溯法。
根据函数递归的性质，在选择一颗子树时，通过“函数调用自身”来进行下层搜索，直到叶子结点，函数将在统计当前路径的价值，比较最大值后自动回溯。

结果

你也可以在下方操作此程序，注意使用英文逗号分隔数字

源程序

var n,w;
var ans=0;
var path = new Array();
var bestpath = new Array();
var a =new Array();

function search(x,wi,vl)
{
    // 如果已经到叶子结点
    if(x>n)
    {
        // 那么检查是否是最优解
        if(vl>ans)
        {
            ans = vl;
            // 是最优解，记录路径
            for(var i = 0; i < n ; i++)
            {
                if(path[i])
                    bestpath[i] = 'Y';
                else
                    bestpath[i] = 'N';
            }
        }
        return;
    }
    path[i] = 1;
    var now = 0;
    for(var j = 0;j<=i;j++)
    {
        if(path[j])
            now+=w[j];
    }
    //  如果还没有超出包的最大重量，那么选择这个节点，并且继续向下搜索
    if(now<=n)
        search(x+1,wi+a.wei[x],vl+a.val[x]);
    // 如果不能选了，就放弃这个节点的左子树，向右子树搜索
    else
    {
        path[i] = 0;
        search(x+1,wi,vl);
    }
}
    document.getElementById("mv").innerHTML = ans;
    document.getElementById("bp").innerHTML = bestpath;
    console.log(ans,bestpath);
}

document.getElementById('submit').onclick = function(event)
{
    // 每次点击按钮 先初始化环境
    n=0;
    w=0;
    ans=0;
    path.splice(0,path.length);
    bestpath.splice(0,bestpath.length);
    a.splice(0,a.length);
    // 总重量，要转换数据类型
    w =parseInt(document.getElementById('w').value);
    // 每个物品的价值
    var v_str =  document.getElementById('val').value ;
    var value = v_str.split( ',' );
    a.val=value.map(Number);
    // 获取物品的个数
    n = a.val.length;
    // 每个物品的重量
    var w_str =  document.getElementById('wei').value ;
    var weight = w_str.split( ',' );
    a.wei= weight.map(Number);

    // 可行性检查
    if(a.val.length == a.wei.length)
    {
        search(0,0,0);
    }
    else
        alert('重量 和 价值 不对应，数目不同。')
}

心得体会

熟能生巧

回溯法运用了函数本身的性质，在一开始我掌握得不太好。但在反复练习后，感受到了其巧妙地运用。
JS调试也是，距离上一次使用JS已经过去了很久。现在再上手真的优点困难。不过在调试中，也学到了一些新的函数。学习中复习，复习中学习。

其他写法

这里给出另一种写法，但由于一直调试欠佳，想看看最开始的程序，在撤销操作保存后，把IDE给关了。程序就被删除了，只有一个旧稿子。暂时只能在源程序写数据。
我实在是不想再调试这个程序了，干脆重写了。原来的就直接放在这里吧。


var c = 100; // 背包最大容量
var n = 5; // 代表有5个物品
var w = [10,20,30,40,60]; //代表5个物品的重量
var v = [20,30,65,40,60]; //代表5个物品的价值
var path = []; // 来记录树中的移动路径，为1的时候表示选择该数据，为0表示不选择
var maxvalue = 0; // 背包的最大权重值
function search(i) { // 表示递归深度
    if(i>=n){
        checkMax(); //检查最大值
    }
    else{
        path[i] = 0;
        search(i+1);
        path[i] = 1;
        var now = 0;
        for(var j = 0;j<=i;j++)
        {
            if(path[j])
                now+=w[j];
        }
        if(now<=n)
            search(i+1);
        else
            return;
    }
}
function checkMax() {
    var weight = 0,
        value = 0;
    for(var i=0;i<n;i++){ 
        if(path[i] == 1){
            weight += w[i];
            value += v[i];
        }
        else{
            path[i] == 0;
        }
    }
    if (weight <= c) { // 判断是否达到上限
        if (value >= maxvalue) {
            maxvalue = value;
            console.log('最大价值为'+maxvalue);
            console.log('所选物品（1为选中，0代表不选）：');
            console.log(path);
        }
    }
}
search(0);

实验五 回溯算法