C++多重背包

有n個物品和一個容量為v的背包，第i中物品最多有n[i]件可用，每件費用是c[i],價值是w[i]。

求将哪些物品裝入背包中課以使這些物品的費用總和不超過背包容量，并且價值總和最大。

可以在01背包問題基礎上去考慮。
           

【題目描述】

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

【輸入】

第一行二個數n(n≤500)，m(m≤6000)，其中n代表希望購買的獎品的種數，m表示撥款金額。
接下來n行，每行3個數，v、w、s，分别表示第I種獎品的價格、價值（價格與價值是不同的概念）
和能購買的最大數量（買0件到s件均可），其中v≤100，w≤1000，s≤10。

【輸出】

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

【輸入樣例】

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

【輸出樣例】

1040
           

仔細體會一下：01背包每種物品隻能裝1件（拿或不拿），完全背包每種物品無限裝，多種背包是每種物品有限裝。

dp[j]：表示目前背包容量為 j 時所能拿到的最大價值（撥款金額為j時，購買最大價值的獎品）
v[i]:物品重量（物品價格）
w[i]:價值
           

#include <iostream>
using namespace std;

int v[500],w[500],s[500],dp[6000];//v:價格，w:價值，s:購買的最大數量 
int main(){
	int n,m;
	cin>>n>>m;// n：購買的獎品的種數  m：撥款金額。
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i]>>s[i];
	}	
	for(int i=1;i<=n;i++){//物品 
		for(int j=m;j>=1;j--){//逆向推，用到上一條的舊資料 
			for(int k=0;k<=s[i] && j>=k*v[i];k++){
				dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);		
			}					
		}
	}
	cout<<dp[m];
	return 0;
}