开心的金明:顺推法

本文主要是介绍开心的金明:顺推法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

分析

设 f[i,j]表示前i件物品，总重量不超过j的最优价值

则 f[i，j]=max{f[i－1，j-w[i]]+P[i]*v[i]，f[i－1，j]）（1<=i<=m,1<=j<=n,j>=w[i]）顺推

F[m,n]即为最优解

var
n,m,i,j:longint;
w:array[1..30000]of longint;
p:array[1..25]of longint;
f:array[0..25,0..30000]of longint;
begin
    read(n);read(m);
    for i:=1 to m do
    readln(w[i],p[i]);
    fillchar(f,sizeof(f),0);
    for i:=1 to m do
    begin
        for j:=1 to n do
        begin
            f[i,j]:=f[i-1,j];
            if (w[i]<=j)and(f[i,j]<=f[i-1,j-w[i]]+p[i]*w[i]) then f[i,j]:=f[i-1,j-w[i]]+p[i]*w[i];
        end;
    end;
    write(f[m,n]);
end.

这篇关于开心的金明:顺推法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---