一个类似背包问题的问题(200分)

一个类似背包问题的问题
有两个数组，data1,data2，每个数组中有n个整数(1=<n<30)，给定一个数M，要求从两个数组中相同下标的两数中各选出一个(即data1与data2中选出一个)，要求这n个数之和最接近M(可以等于，但不能大于)。打印出每组数以及每个数所在组号。(如果存在多组)
不知道表达清楚没有，举一个例子:
n=3 M=16 data1={5,6,9} data2={2,4,6}，我们可以选出{5,4,6}和为15，每个数所在组号也就是{1,2,2}
呵呵，一时间又不知道怎么实现了，希望哪位朋友能够指教!(希望LeeChange之类的高手帮忙)

其实这题的搜索空间不是很大。首先，n<=30，其次，每个结点只有两种扩展方式，要么1要么2。
只是，一般求最优解的题目很少同时要求求所有解。如果先用分支定界求出最优解，再用深度优先求所有解，显然是一种浪费。不如直接按照求所有可行解的方法用深度优先，只是多一个操作，将所有可行解保存起来，全部求完后，在输出可行解中代价等于最优解的解集。

program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
n = 3;
m = 16;
Data1: array [1..n] of Integer = (5, 6, 9);
Data2: array [1..n] of Integer = (2, 4, 6);
type
TAnswer = record
Answer: array [1..n] of Byte;
Sum: Integer
end;

TNode = record
Sum: Integer;
d: Byte
end;

var
Answers: array of TAnswer;
Stack: array [0..n] of TNode;
Top: Integer;
Max: Integer;
Temp: Integer;
i, j: Integer;
begin
FillChar(Stack[0], SizeOf(TNode), 0);
Top:=1;
FillChar(Stack[Top], SizeOf(TNode), 0);
while Top>0do
begin
while Stack[Top].d<2do
begin
Inc(Stack[Top].d);
if Stack[Top].d=1 then
Temp:=Data1[Top]
else
if Stack[Top].d=2 then
Temp:=Data2[Top];
if Stack[Top-1].Sum+Temp<=m then
begin
Stack[Top].Sum:=Stack[Top-1].Sum+Temp;
if Top=n then
begin
SetLength(Answers, Length(Answers)+1);
Answers[Length(Answers)-1].Sum:=Stack[Top].Sum;
for i:=1 to Topdo
Answers[Length(Answers)-1].Answer:=Stack.d
end
else
begin
Inc(Top);
Stack[Top].d:=0
end
end
end;
Dec(Top)
end;

if Length(Answers)>0 then
begin
Max:=0;
for i:=0 to Length(Answers)-1do
if Answers.Sum>Max then
Max:=Answers.Sum;
for i:=0 to Length(Answers)-1do
if Answers.Sum=Max then
begin
for j:=1 to ndo
Write(Answers.Answer[j], ' ');
WriteLn
end
end
else
WriteLn('Not found!');
ReadLn
end.

感谢LeeChange的解答与程序，非常感谢。
还有一个不情之请，能否把您的程序改成一个递归的版本(个人感觉容易理解一些)？

。。。。“关注！“。。。。

program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
n = 3;
m = 16;
Data1: array [1..n] of Integer = (5, 6, 9);
Data2: array [1..n] of Integer = (2, 4, 6);
type
TArr = array [1..n] of Byte;
TAnswer = record
Answer: TArr;
Sum: Integer
end;

var
Answers: array of TAnswer;
Temp: TArr;
Max: Integer;
i, j: Integer;
procedure TryNext(Sum, Step: Integer);
var
d: Byte;
t: Integer;
begin
for d:=1 to 2do
begin
if d=1 then
t:=Data1[Step]
else
t:=Data2[Step];
if Sum+t<=m then
begin
Temp[Step]:=d;
if Step=n then
begin
SetLength(Answers, Length(Answers)+1);
Answers[Length(Answers)-1].Sum:=Sum+t;
for i:=1 to ndo
Answers[Length(Answers)-1].Answer:=Temp
end
else
TryNext(Sum+t, Step+1)
end
end
end;

begin
TryNext(0, 1);
if Length(Answers)>0 then
begin
Max:=0;
for i:=0 to Length(Answers)-1do
if Answers.Sum>Max then
Max:=Answers.Sum;
for i:=0 to Length(Answers)-1do
if Answers.Sum=Max then
begin
for j:=1 to ndo
Write(Answers.Answer[j], ' ');
WriteLn
end
end
else
WriteLn('Not found!');
ReadLn
end.

接受答案了.