All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Final voyage
Tag(s):

Algorithms, Dynamic Programming, Easy

Problem
Editorial
Analytics

"RMS Lusitania" was one of the world biggest ship of her time.On the outbreak of the First World War in 1914, she was commandeered by the Admiralty as an armed merchant cruiser. When Lusitania left New York for Liverpool on what would be her final voyage on 1 May 1915, submarine warfare was intensifying in the Atlantic. Germany had declared the seas around the United Kingdom to be a war-zone..On the afternoon of May 7, Lusitania was bombarded by a German U-Boat,few miles off the southern coast of Ireland and inside the declared “zone of war”.Lusitania was officially carrying among her cargo rifle/machine-gun ammunition, shrapnel artillery shells without powder charges and artillery fuses.Captain "Dow" of Lusitania sensed the danger before and ordered his men to save the ammunition materials as much as they can.

They had few small boats and the overall load those small boats could carry was "W".Captain "Dow" knew the value of all the "N" ammunition items.So he told his men the weight "\(W_i\)" and value "\(V_i\)" of each ammunition item.As it is too difficult to save all the ammunition,Captain then asked his men to smarty choose ammunition items such that the total weight of the ammunition is less than or equal to maximum load those small ships can afford and the corresponding total value of ammunitions saved is maximum.

INPUT:

the first line contain number of testcases "T"."T" testcases follows then.For each testcase,the first line contains the number of ammunition items "N",the second line contains the maximum load "W" those small ships can afford.The third line contains the individual weight of each ammunition item.Then the next line contains the value "V" of those "N" ammunition items.

OUTPUT:

for each testcase output the maximum value of the ammunitions that can be saved.

Constraint:

\(1 \le T \le 100\)

\(0 \le N \le 1000\)

\(1 \le maximum\; load \le 1000\)

\(1 \le weight\; of\; individual\; items \le 1000\)

\(1 \le value\; of\; individual\; items \le 1000\)

SAMPLE INPUT
2
3 
3
1 2 3     
2 4 8
4 
8
2 4 5 7
4 9 7 5
SAMPLE OUTPUT
8
13
Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

CommonFloor

Challenge Name

CommonFloor Backend Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?