leechange请进，请教您写的背包问题程序 (100分)

我正在拜读您写的背包问题程序。
呵呵，已经比较喜欢您的栈模拟递归的风格了。
问题：背包问题求解 ( 积分：50, 回复：7, 阅读：103 )
分类：数据结构 ( 版主：creation-zy, 张剑波 )
来自：xwg95, 时间：2003-3-24 2:55:00, ID：1704917 [显示：小字体 | 大字体]
假设有n件物品，记作d1,d2,...,dn，对应于每个物品都有一个正整数重量w和一个正整数
价值v，如何从这n件物品中挑选某几件物品放进背包，使总重量不超过给定的重量p，同时
使背包中的物品的价值尽可能高。假设此n件物品的相对价值：v1/w1,v2/w2,...,vn/wn是
按递减次序排列的，且所有物品的总重量大于背包所能承受的重量p，且最轻物品的重量dn
小于p。求算法，最好用c语言描述。

您的程序如下：我的问题以Q1,Q2的形式提出
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxN = 255;
type
TArticle = record
w: Integer;
v: Integer;
OldIndex: Integer;
p:do
uble
end;

TNode = record
d: Integer;
UsedArticles: set of Byte;
v: Integer;
p: Integer
end;

var
N: Integer;
P: Integer;
Articles: array [1..MaxN] of TArticle;
Top: Integer;
Stack: array [1..MaxN] of TNode;
Node: TNode;
Best: array [1..MaxN] ofdo
uble;
BetterSet: set of Byte;
BetterV: Integer;
procedure Init;
var
i, j: Byte;
t: TArticle;
PP: Integer;
begin
Write('N: ');
ReadLn(N);
for i:=1 to Ndo
begin
Write('w[', i, ']:');
ReadLn(Articles.w);
Write('v[', i, ']:');
ReadLn(Articles.v);
Articles.p:=Articles.v/Articles.w;
Articles.OldIndex:=i
end;
Write('P: ');
ReadLn(P);
for i:=1 to N-1do
for j:=i+1 to Ndo
if Articles.p<Articles[j].p then
begin
t:=Articles;
Articles:=Articles[j];
Articles[j]:=t
end;

Best[1]:=0;
for i:=2 to Ndo
Best[1]:=Best[1]+Articles.v;
for i:=2 to Ndo
Best:=Best[i-1]-Articles.v;
//Q1:Best数组有什么作用?为什么Articles[1].v没有加入？
PP:=P;
BetterSet:=[];
BetterV:=0;
for i:=1 to Ndo
if Articles.w<=PP then
begin
BetterSet:=BetterSet+;
BetterV:=BetterV+Articles.v;
PP:=PP-Articles.w
end;

Top:=1;
Stack[Top].d:=0;
Stack[Top].UsedArticles:=[];
Stack[Top].v:=0;
Stack[Top].p:=P
end;

procedure Print;
var
i: Integer;
begin
Write('Sum: ', BetterV,'. ');
for i:=1 to Ndo
if (i in BetterSet) then
Write(' ', Articles.OldIndex);
ReadLn
end;

begin
Init;
while Top>0do
begin
while Stack[Top].d<Ndo
begin
Inc(Stack[Top].d);
if Articles[Stack[Top].d].w<=Stack[Top].p then
begin
Node:=Stack[Top];
Node.UsedArticles:=Node.UsedArticles+[Node.d];
Node.v:=Node.v+Articles[Node.d].v;
Node.p:=Node.p-Articles[Node.d].w;
if Top=N then
begin
if Node.v>BetterV then
begin
BetterV:=Node.v;
BetterSet:=Node.UsedArticles
end
end
else
if (Node.v+Best[Node.d])>BetterV then
//Q2: (Node.v+Best[Node.d])这两个数相加分别有什么意义?
begin
if Node.v>=BetterV then
begin
BetterV:=Node.v;
BetterSet:=Node.UsedArticles
end;
Inc(Top);
Stack[Top]:=Node
end
end
end;
Dec(Top)
end;
Print
end.

等待您的解答!

Q1:Best表示∑Vj(i<j<=n),就是i之后的所有物品的总价值。
Q2:
Node.v是当前方案背包中所有物品的总价值
Node.d是背包中最后一个放入的物品。
Best[Node.d]是Node.d之后所有物品的总价值
Node.v+Best[Node.d]就是对当前的方案做最乐观的估计（后面所有的物品都能放入背包）。
if (Node.v+Best[Node.d])>BetterV then
的意思是，如果对当前方案做最乐观估计都不会比已经得到的方案好，就不扩展当前状态。反过来说，就是当前方案有可能获得更优的解，才扩展。

呵呵，原来如此，谢谢Leechange。