求PASCAL背包问题和无限背包思路和程序

求PASCAL背包问题和无限背包思路和程序
求PASCAL背包问题和无限背包思路和程序

求PASCAL背包问题和无限背包思路和程序
01背包：
fillchar(f,sizeof(f),0);{f数组初始化为0}
read(数量,总钱数);
for i:=1 to 数量 do begin
read(价钱,价值);
for j:=总钱数 DOWNTO 价钱 do
if f[j]=0)and(f[i]=best then exit;
{s[n]为前n个物品的重量和}
if k< =n then begin
if v >w[k] then search(k+1,v-w[k]);
search(k+1,v);
end;
end;
l DP
F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志,为布尔型.
实现:将最优化问题转化为判定性问题
F[I,j]=f[i-1,j-w[i]] (w[I]< =j< =v) 边界：f[0,0]:=true.
For I:=1 to n do
For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];
优化：当前状态只与前一阶段状态有关,可降至一维.
F[0]:=true;
For I:=1 to n do begin
F1:=f;
For j:=w[I] to v do
If f[j-w[I]] then f1[j]:=true;
F:=f1;
End;
B.求可以放入的最大价值.
C.求恰好装满的情况数.
(2)每个背包可使用任意次：
A.求最多可放入的重量.
状态转移方程为
f[I,j]=max{f[i-w[j]
B.求可以放入的最大价值.
USACO 1.2 Score Inflation
进行一次竞赛,总时间T固定,有若干种可选择的题目,每种题目可选入的
数量不限,每种题目有一个ti（解答此题所需的时间）和一个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]);
End.