时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。
*易想到：
f[i,j] = max { f [i- k*w[j], j-1] + k*v[j] } (0< =k< = i div w[j])
其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。
*优化：
Begin
FillChar(problem,SizeOf(problem),0);
Assign(Input,''inflate.in'');
Reset(Input);
Readln(M,N);
For i:=1 To N Do
With problem[i] Do
Readln(point,time);
Close(Input);

FillChar(f,SizeOf(f),0);
For i:=1 To M Do
For j:=1 To N Do
If i-problem[j].time >=0 Then
Begin
t:=problem[j].point+f[i-problem[j].time];
If t >f[i] Then f[i]:=t;
End;

Assign(Output,''inflate.out'');
Rewrite(Output);
Writeln(f[M]);
Close(Output);
End.
C.求恰好装满的情况数。
Ahoi2001 Problem2
求自然数n本质不同的质数和的表达式的数目。
思路一，生成每个质数的系数的排列，在一一测试，这是通法。
procedure try(dep:integer);
var i,j:integer;
begin
cal; {此过程计算当前系数的计算结果，now为结果}
if now >n then exit; {剪枝}
if dep=l+1 then begin {生成所有系数}
cal;
if now=n then inc(tot);
exit;
end;
for i:=0 to n div pr[dep] do begin
xs[dep]:=i;
try(dep+1);
xs[dep]:=0;
end;
end;

思路二，递归搜索效率较高
procedure try(dep,rest:integer);
var i,j,x:integer;
begin
if (rest< =0) or (dep=l+1) then begin
if rest=0 then inc(tot);
exit;
end;
for i:=0 to rest div pr[dep] do
try(dep+1,rest-pr[dep]*i);
end;

思路三：可使用动态规划求解
USACO1.2 money system
V个物品，背包容量为n，求放法总数。
转移方程：

Procedure update;
var j,k:integer;
begin
c:=a;
for j:=0 to n do
if a[j] >0 then
for k:=1 to n div now do
if j+now*k< =n then inc(c[j+now*k],a[j]);
a:=c;
end;
{main}
begin
read(now); {读入第一个物品的重量}
i:=0; {a[i]为背包容量为i时的放法总数}
while i< =n do begin
a[i]:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1，作为初值}
for i:=2 to v do
begin
read(now);
update; {动态更新}
end;
writeln(a[n]);

7.排序算法
A.快速排序：
procedure sort(l,r:integer);
var i,j,mid:integer;
begin
i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数}
repeat
while a[i]< mid do inc(i); {在左半部分寻找比中间数大的数}
while mid< a[j] do dec(j);{在右半部分寻找比中间数小的数}
if i< =j then begin {若找到一组与排序目标不一致的数对则交换它们}
swap(a[i],a[j]);
inc(i);dec(j); {继续找}
end;
until i >j;
if l< j then sort(l,j); {若未到两个数的边界，则递归搜索左右区间}
if i< r then sort(i,r);
end;{sort}
　

B.插入排序：
procedure insert_sort(k,m:word); {k为当前要插入的数，m为插入位置的指针}
var i:word; p:0..1;
begin
p:=0;
for i:=m downto 1 do
if k=a[i] then exit;
repeat
If k >a[m] then begin
a[m+1]:=k; p:=1;
end
else begin
a[m+1]:=a[m]; dec(m);
end;
until p=1;
end;{insert_sort}
l 主程序中为：
a[0]:=0;
for I:=1 to n do insert_sort(b[I],I-1);

C.选择排序：
procedure sort;
var i,j,k:integer;
be