求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 kif 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]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其中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.求恰好装满的情

我好好复习下

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息