UC知道求noip开心的金明题解！（有答案）
来源：百度知道 编辑：UC知道 时间：2024/05/30 11:38:00
我有这道题的程序，但是不是很懂，我需要解释！感谢各位大哥大姐，帮帮忙吧！如果有更好的程序，请也教教我，谢谢！
注意：本人是初学者。
const maxt=1000;maxm=10;
var i,j,m,N,k,l,sum:integer;
v,p:array[1..maxm] of integer;
s:array[0..maxm,0..maxt] of longint;
function happy(x,y:integer):integer;
begin
if x>y then
happy:=x
else
happy:=y;
end;
begin
assign(input,'happy.in');
reset(input);
read(N,m);
for i:=1 to m do
for j:=1 to n do
s[i,j]:=0;
for i:=1 to m do readln(v[i],p[i]);
for i:=1 to m do
for j:=1 to N do
if j>=v[i] then begin
s[i,j]:=happy((s[i-1,j-v[i]]+v[i]*p[i]),s[i-1,j]);
end
else
s[i,j]:=s[i-1,j];
assign(output,'happy.out');
rewrite(output);
write(s[m,N]);
close(input);
close(output);
end.
注意：本人是初学者。
const maxt=1000;maxm=10;
var i,j,m,N,k,l,sum:integer;
v,p:array[1..maxm] of integer;
s:array[0..maxm,0..maxt] of longint;
function happy(x,y:integer):integer;
begin
if x>y then
happy:=x
else
happy:=y;
end;
begin
assign(input,'happy.in');
reset(input);
read(N,m);
for i:=1 to m do
for j:=1 to n do
s[i,j]:=0;
for i:=1 to m do readln(v[i],p[i]);
for i:=1 to m do
for j:=1 to N do
if j>=v[i] then begin
s[i,j]:=happy((s[i-1,j-v[i]]+v[i]*p[i]),s[i-1,j]);
end
else
s[i,j]:=s[i-1,j];
assign(output,'happy.out');
rewrite(output);
write(s[m,N]);
close(input);
close(output);
end.
这道题为经典的0-1背包问题，使用动态规划或搜索均可解决。但考虑搜索效率的问题，还是动态规划较好一些。
若用f[i]表示当前用i元能取得的最大收益，w[i]表示物品重要度，p[i]表示物品价格，c[i]:=w[i]*p[i]，则此题中，p为花费，c为收益。动态转移方程为：
f[i]=max{f[i],f[i-p[j]]+c[j]}
在你的标程中，s[i,j]表示在考虑前i件物品且只有j元时所能取得的最大收益。
s[i,j]:=happy((s[i-1,j-v[i]]+v[i]*p[i]),s[i-1,j]);
此行程序中，"happy"为判断大小的函数，返回两个参数中较大的一个；买不买第i件物品被讨论。若买了，则要花去v[i]元，获得v[i]*p[i]的收益；若不买，则没有变化，仍然与讨论完上一件物品的情况一样。
s[i,j]取其中较大的一个。