Knapsack 3 - MarisaOJ: Marisa Online Judge

There are

$n$ type of items,

$i^{th}$ type item has the weight of

$w_i$ , value of

$v_i$ , and a quantity of

$a_i$ . You can choose an arbitrary number items as long as their weight doesn't exceed a given

$S$ . Find a way of choosing items so that their value is maximum possible. ### Input - First line contains 2 integers

$n$ and

$S$ . - Each line in the next

$n$ line contains three integers

$w_i, v_i,a_i$ . ### Output - The maximum possible value you can obtain. ### Constraints -

$1 \le n \le 100, S \le 10^4$ . -

$1 \le w_i, v_i,a_i \le 10^4$ . ### Example Input:

$3 4 1 4 2 2 7 2 3 6 1$

Output:

$15$

Introduction to Dynamic Programming (Part two)
	Sake game
	Coins
	Coins 2
	Game on array
	Longest increasing subsequence 2
	Convolution
	Regular bracket sequence
	Faulty addition
	Weird bank
	Delete operation
	Palindromize
	Color ribbon
	Unique subsequences
	Unique subsequences 2
	Cow exhibition
	Knapsack 3
	Compressing array
	Regular bracket sequence 2
	Maximum path 3
	Concating substring
	Soil
	Stacking boxes
	String transformation
	Palindromic quadruple
	Finding teammates

Topic

Dynamic Programming

Rating

1600

Source

VNOJ

Solution (0)

Solution