題意

設有n 種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為M，今從n 種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于M，而價值的和為最大。

分析

f[j]:=max(f[j],f[j-w[i]]+p[i];

最大價值=f[m];

var
w,p:array[0..30]of longint;
f:array[0..300]of longint;
n,m,i,j:longint;
begin
? ? readln(m,n);
? ? for i:=1 to n do
? ? readln(w[i],p[i]);
? ? fillchar(f,sizeof(f),0);
? ? for i:=1 to n do
? ? begin
? ? ? ? for j:=0 to m do
? ? ? ? begin
? ? ? ? ? ? if (j>=w[i]) then
? ? ? ? ? ? if f[j]>f[j-w[i]]+p[i] then f[j]:=f[j] else f[j]:=f[j-w[i]]+p[i];
? ? ? ? end;
? ? end;
? ? write(f[m]);
end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500173.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的完全背包：一维数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。