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 
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<