多重背包-模板

#include<iostream>
using namespace std;
const int N =1001;
int dp[N],w[N],v[N],c[N];//定义dp数组，体积，价值，数量
int n,m; 
int main(){
	cin>>m>>n;//先输入背包容量，再是件数
	//输入物品信息 
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>c[i];
	} 
	//开始多重！！！
	for(int i=1;i<=n;i++){//遍历n种物品
		for(int j=m;j>=1;j--){//遍历背包容量m 
			for(int k=c[i];k>=0;k--){//遍历每种物品件数
				if(j>=k*w[i])//不是一定能装得下，得判断 
					dp[j] = max(dp[j],dp[j-k*w[i]] + k*v[i]); 
			} 
		} 
	}
	cout<<dp[m];
	return 0;
}