Description

背包體積為V ,給出N個物品，每個物品占用體積為Vi,價值為Wi,每個物品要么至多取1件，要么至多取mi件（mi > 1） , 要么數量無限 ， 在所裝物品總體積不超過V的前提下所裝物品的價值的和的最大值是多少？

Input

第一行兩個數V,N下面N行每行三個數Vi,Wi,Mi表示每個物品的體積，價值與數量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=0表示數量無限

Output

1個數Ans表示所裝物品價值的最大值

Sample Input

10 3 2 1 0 3 3 1 4 5 4

Sample Output

11

分析

這題把01背包、完全背包、多重背包疊加在一起，在循環的時候判斷一下是哪一種，就去做哪一種。

• var v,n,i,j,k:longint; t,w,m:array[0..30]of longint; f:array[0..200]of longint;function max(a,b:longint):longint; beginif a>b then exit(a) else exit(b); end;beginreadln(v,n);for i:=1 to n doreadln(t[i],w[i],m[i]);for i:=1 to n dobeginif m[i]=0 thenbeginfor j:=t[i] to v dof[j]:=max(f[j],f[j-t[i]]+w[i]);end elsebeginfor j:=1 to m[i] dofor k:=v downto t[i] dof[k]:=max(f[k],f[k-t[i]]+w[i]);end;end;write(f[v]); end.

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

總結

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

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