实验五 回溯算法

实验目的

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

实验要求

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

实验内容

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

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

思路

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

具体些

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

如何回溯

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

结果

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

回溯法求0-1背包

最大载重
   价值   
   重量   
             

回溯法求最优价值：155
回溯法求出的最优选择：Y,Y,Y,Y,N

源程序

    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);