实验五 回溯算法

实验目的

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

实验要求

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

实验内容

问题描述:有 nn 种物品,每种物品只有 11 个。第 ii 种物品价值为 viv_i,重量为 wiw_ii=1,2,,ni = 1, 2, \dots, n。问如何选择放入背包的物品,使得总重量不超过 BB,而价值达到最大?

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

思路

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

具体些

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

如何回溯

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

结果

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

回溯法求0-1背包 最大载重
   价值   
   重量   
             

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

源程序

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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给关了。程序就被删除了,只有一个旧稿子。暂时只能在源程序写数据。
我实在是不想再调试这个程序了,干脆重写了。原来的就直接放在这里吧。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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