背包问题求解(50分)

假设有n件物品，记作d1,d2,...,dn，对应于每个物品都有一个正整数重量w和一个正整数
价值v，如何从这n件物品中挑选某几件物品放进背包，使总重量不超过给定的重量p，同时
使背包中的物品的价值尽可能高。假设此n件物品的相对价值：v1/w1,v2/w2,...,vn/wn是
按递减次序排列的，且所有物品的总重量大于背包所能承受的重量p，且最轻物品的重量dn
小于p。求算法，最好用c语言描述。

是NPC问题,给出一种比较好的近似算法,对出n件物品分割成不多于d个元素的集合再搜索:
MaxSize = 0;
Result <- 空集;
for (i = 0;
i <= d;
i++){
for (集合R中的k(0 <= i <= d )个元素的){
s = ΣR[k];

selected = Σk;
}
for (其他未被选入R中的元素j)
if (s + R[j] < = p){
s = s + R[j];
selected <- j;
}
if (s >= MaxSize){
MaxSize = s;
Result = selected;
}
if (s = p){
输出MaxSize, Result;
break;
}
}
规模是O(n^d)

可以考虑用模拟退火算法。

采用递归方法很容易解决

hehe,这题可不叫背包问题，叫0，1背包问题。
背包问题是能用贪心法解的。
0，1背包一般来说是要搜索的。

呵呵，昨天刚看到西安交大的《遗传算法——理论、应用与软件实现》中以该问题为例进
行了算法分析。——书上说这个问题就是“背包问题”（而背包问题的数学模型就是“0-1
规划问题”） 采用“二重结构编码”的遗传算法要比普通的SGA优越得多。
可惜，书上只是进行了理论分析，没有给出代码...

to creation-zy:
能否详细谈谈“二重结构编码”,或者提供相关的资料.谢谢.

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;
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
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.
找到Bug请速通知我.

多人接受答案了。