All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?