Class notes (3) example (2) -567 Beanfeast

Description

In order to celebrate the class's first place in the school sports meeting , The head teacher decided to hold a celebration meeting , For this purpose, allocate funds to buy prizes to reward athletes . It is expected that the allocation amount can buy the most valuable prize , It can replenish their energy and physical strength .

Format

Input

Two numbers in the first line n (n≤500),m (m≤6000), among  n Represents the number of prizes you want to buy ,m Indicates the appropriation amount .

Next  n That's ok , Each row  3 Number ,v、w、s, Separate indication control  ii  The price of each prize 、 value （ Price and value are different concepts ） And the number of purchases （ buy  0 Pieces arrive at  s Pieces can be ）, among v≤100,w≤1000,s≤10.

Output

a number , Indicates the maximum value that can be obtained from this purchase （ Be careful ！ It's not the price ）.

Samples

input data 1

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

Output data 1

1040

Limitation

1s, 1024KiB for each test case.

Answer key ：

This is a classic multiple knapsack problem , Thinking table ~

With the formula in the table, plus three cycles and judgment conditions, it can be completed .

Program ：

#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++){// Traverse n Items   
		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;
}

be without ？ be without ！