Description

為了慶賀班級在校運動會上取得第一名的成績，班主任決定開一場慶功會，為此拔款購買獎品獎勵運動員，期望拔款金額能購買最大價值的獎品，可以補充他們的精力和體力。

Input

第一行二個數(shù)n(n<=500)，m(m<=5000)，其中n代表希望購買的物品的種數(shù)，m表示班會撥的錢數(shù)。
接下來n行，每行3個數(shù)，v、w、s，分別表示第I種物品的價格、價值（價格 與 價值 是不同的概念）和購買的數(shù)量（只能買0件或s件），其中v<=100,w<=1000,s<=10

Output

第一行：一個數(shù)，表示此次購買能獲得的最大的價值（注意！不是價格）。

Sample Input

5 1000 80 20 4 40 50 9 30 50 7 20 20 1

Sample Output

1040

分析

這題其實是多重背包。

設(shè)f[j]為重量為j時所得的最大價值 f[j]:=max(f[j],f[j-k*v[i]]+w[i]*k);

• var n,m,i,j,k:longint; s,w,v:array[0..500]of longint; f:array[-100..6000]of longint; function max(a,b:longint):longint; beginif a>b then exit(a) else exit(b); end;beginreadln(n,m);for i:=1 to n doreadln(v[i],w[i],s[i]);for i:=1 to n dofor j:=m downto 0 dofor k:=0 to s[i] dobeginif j-k*v[i]<0 then break;f[j]:=max(f[j],f[j-k*v[i]]+w[i]*k);end;write(f[m]); end.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500140.html

總結(jié)

以上是生活随笔為你收集整理的庆功会(多重背包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。