題意

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

分析

if (i>=w[j]) then t:=f[i-w[j]]+p[j];
if t>f[i] then f[i]:=t;

結果=f[m];

var
w,p:array[0..30]of longint;
f:array[0..300]of longint;
n,m,i,j,t: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 m do
? ? begin
? ? ? ? for j:=1 to n do
? ? ? ? begin
? ? ? ? ? ? if (i>=w[j]) then t:=f[i-w[j]]+p[j];
? ? ? ? ? ? if t>f[i] then f[i]:=t;
? ? ? ? end;
? ? end;
? ? write(f[m]);
end.

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

總結

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

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