Knapsacks
/

## Algorithms, Dynamic Programming

Problem
Editorial
Analytics

You are given $n$ objects, a knapsack of capacity $c$, array $v$, and array $w$. The $i^{th}$ object has value v[i] and weight w[i].

Determine the maximum total value that you can get by selecting objects in such a manner that their sum of weights is not greater than the capacity $c$.

Input format

• First line: Two integers $n$ and $c$ denoting the number of objects and capacity of the knapsack ($1 \le n \le 10^3$ and $0 \le c \le 2×10^6$
• Second line: $n$ integers $v_1,\ v_2,\ ..., v_n$ ($0 \le v_i \le 50$)
• Third line: $n$ integers $w_1,\ w_2,\ ...,\ w_n$ ($0 \le w_i \le 2×10^6$)

Output format

Print a single integer denoting the maximum value that you can get by selecting the objects.

SAMPLE INPUT
4 20
10 2 1 3
10 5 10 10

SAMPLE OUTPUT
13

Explanation

Optimal selection is 1st and 4th object. Total value=(10+3)=13 Total weight=(10+10)=20. Total weight <= Capacity.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...