[问题描述] 背包是一个简单的递归问题,要求是从n件物品中抽取几件,使之质量一定.该程序只求一组解.
输入:[KEYBOARD] 输出:[SCREEN]
10
1 2 3 4 5 6 7 8 9 12
9
--------------------------
5
1 2 3 4 5
45
2 3 4

------------------
NO ANSWER!


[问题分析] 使用递归算法完成.每件物品只有放入,不放入两种情况.

program knapProg;

const m=5;
var item:array[1..m] of integer;
i,w:integer;

function knap(a,b:integer):boolean;
begin
if item[a]=b then begin knap:=true;write(item[a]:8);exit;end;
if ((item[a]>b) and (a=m)) then begin knap:=false;exit;end;
if knap(a+1,b-item[a]) then begin knap:=true;write(item[a]:8);exit;end;
if not knap(a+1,b) then knap:=false;
end;

begin
writeln('Please input item weights:');
for i:=1 to m do read(item[i]);
writeln('Total weight:');
readln(w);
writeln;
if not knap(1,w) then writeln('NO ANSWER!!');
readln;
end.