上课笔记(3)例题(2)——＃567. 庆功会(beanfeast)

Description

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

Format

Input

第一行二个数 n (n≤500)，m (m≤6000)，其中 n 代表希望购买的奖品的种数，m 表示拨款金额。

接下来 n 行，每行 3 个数，v、w、s，分别表示第 ii 种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买 0 件到 s 件均可），其中 v≤100，w≤1000，s≤10。

Output

一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

Samples

输入数据 1

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

输出数据 1

1040

Limitation

1s, 1024KiB for each test case.

题解：

这是一道经典的多重背包问题，思考表格献上~

用上表格里的公式再加上三循环和判断条件就可以完成了。

程序：

#include<bits/stdc++.h>
using namespace std;
int m,n,a[510],w[510],c[510],dp[6010];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>w[i]>>c[i]>>a[i];		
	for(int i=1;i<=n;i++){//遍历n个物品  
		for(int j=m;j>=w[i];j--){
			for(int k=0;k<=a[i];k++){
				if(j-k*w[i]<0)
					break;
				dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
			}
		}
	}
	cout<<dp[m];
	return 0;
}

没了？没了！