文档介绍：会计学
1
Pascal算法背包问题析
0-1背包问题
所谓的背包问题，可以描述如下：
一个小偷打劫一个保险箱，发现柜子里有N个不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。我们标识每个物品的价为ＶI,大小是ZI
第1页/共20页
算法描述
对于0/1背包相关的问题我们有多种方法可以解决
⑴贪心法
⑵搜索法(回溯)
(3)递归
⑷动态规划
第2页/共20页
⑴ 贪心法
贪心算法描述:
总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。
应用：
1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。但是这种思路是否可以解决问题
2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。
第3页/共20页
该题设计的贪心算法
利用贪心算法的定义，我们定义一个数组变量A[I]:=V[I]/Z[I]来表示每件物品的单位体积的价值,然后按照单位体积的价值进行从大到小的排序,小偷取东西的时候的策略先取单位体积价值最高的物品,一直到背包不能再放物品为止;
该算法的分析:
该算法简单,,”采药”这一题中应该有清醒的认识!
第4页/共20页
参考程序段
For i:=1 to n do A[I]:=V[I]/Z[I]//求单位价值
For i:=1 to n-1 do
for j:=i+1 to n do
If a[i]<a[j] then begin v[i]<->v[j];z[i]<->z[j];A[I]<->A[J];end;
//按照单位价值的从大到小排列；
i:=1;v:=0;
While m>a[i] do
Begin V:=v+v[i]; M:=m-z[i]; i:=i+1;end;
//按照单位价值从大到小取物品
Writeln(‘the total value is’,v);
//上面的题目存在什么问题,该怎么去解决它
第5页/共20页
⑵搜索法
搜索算法介绍：
经过对题目的分析我们可以的出下列结论，对于每个物品来说我们只有两中状态取或者不取，也就是一个背包的解就是一个长小于Ｎ的决策序列，这个序列是有（０,1)组成，所以我们可以利用回溯的原理将所有的背包的所有可能列举出来，然后在所有的可能性中找到最优的解；
第6页/共20页
一：回溯的概念
从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。
回溯算法是一种有条不紊的搜索问题答案的方法，是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。常用于查找问题的解集或符合某些限制条件的最佳解集。
第7页/共20页
二、回溯的通用描述算法
program 程序名；
const maxdepth=xxx;
type statetype=****; {状态类型定义}
var stack:array[1..maxdepth] of statetype; {存当前路径}
total:integer; {路径数}
procedure make(k:integer); {递归搜索以stack[k]为初始接点的所有路径}
var i:integer; {子节点个数}
begin
if stack[k-1]是目标状态 then
begin
total:=total+1;
输出当前路径stack[1]..stack[k-1];
exit; {回溯（如果只需要一条路径，则exit改为halt即可）}}
end;
for i:=算符最小值 to 算符最大值 do
begin
算符i作用于生成stack[k-1]产生子状态stack[k];
if stack[k]满足约束条件 then make(k+1);{若不满足，则通过for循环换一个算符扩展；递归返回该处时，系统自动恢复调用前的栈指针