10 100 10 100 10 10
- 样例输出 201
程序如下： var
a:array[1..20,1..20]of integer; b:array[1..20]of boolean; d:array[0..21]of integer; max,n,i,j:integer; f:text;
procedure step(x,s:integer); var
i,j:integer; begin
if s+d[x+1]<=max then exit; if x>n then
if s>max then begin max:=s; exit;end; for i:=1 to n do if b[i] then begin b[i]:=false;
step(x+1,s+a[x,i]); b[i]:=true; end; end; begin
assign(f,'input.in'); reset(f); readln(f,n); for i:=1 to n do begin
for j:=1 to n do read(f,a[i,j]); readln(f); end; close(f);
加展望 d[n+1]:=0;
for i:=n downto 1 do begin
d[i]:=a[i,1]; for j:=2 to n do
if a[i,j]>d[i] then d[i]:=a[i,j]; d[i]:=d[i]+d[i+1]; end; max:=0;
fillchar(b,sizeof(b),true); step(1,0); writeln(max); end.
２、 背包问题（0~1）要么装，要么不装，不允许切割。 （1）设有一个背包可以放入的物品重量为V，现有n件物品，重量分别为W1,W2,...Wn。问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和最接近或正好为V。（不允许重复） 变式：
装箱问题
问题描述
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30＝，每个物品有一个体积（正整数）。（允许重放）
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 样例 输入：
24 一个整数，表示箱子容量 6 一个整数，表示有n个物品
8 接下来n行，分别表示这n 个物品的各自体积 3 12 7 9 7
输出：
0 一个整数，表示箱子剩余空间。（要么为0，要么为一个较小的
数）
程序如下:
uses dos;
var a:array[1..50] of integer; b:array[0..50] of integer; v,n,min:integer; h,f,m,m1:word; procedure init; var f:text;
i,j,k:integer; begin
assign(f,'10.txt'); reset(f); readln(f,v); readln(f,n);
for i:=1 to n do readln(f,a[i]); close(f);
for i:=1 to n-1 do for j:=i+1 to n do
if a[i]
procedure try(k,s:integer); var i:integer; begin
if s
try(k+1,s-a[i]); end; end;
begin
gettime(h,f,m,m1);
writeln(h,':',f,':',m,':',m1); init; min:=v; b[0]:=0; try(1,v);
writeln(min);
gettime(h,f,m,m1);
writeln(h,':',f,':',m,':',m1); end.
程序如下：
３、 背包问题，求背包的价值值最大。?
n个物品重量和价值对应关系如图所示，求价值最大。
三、采药 (medic.pas/c/cpp)
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】 70 3 71 100 69 1 1 2
【样例输出】 3
【数据规模】
对于30%的数据，M <= 10； 对于全部的数据，M <= 100。