0-1 Knapsack Problem
A thief is planning to rob a store and has a knapsack that can carry a maximal weight of W
. There are N
items available, where each item i
has a weight wi
and a value vi
. Determine the maximum total value of items the thief can carry without exceeding the weight limit of the knapsack.
Input:
The first line contains a single integer T
, representing the number of test cases.
For each test case, the input consists of:
- An integer
N
, denoting the number of items.
N
space-separated integers representing the weights of the items.
N
space-separated integers representing the values of the items.
- An integer
W
, denoting the maximum capacity of the knapsack.
Output:
For each test case, output a single integer representing the maximum value that can be attained without exceeding the knapsack's weight capacity. Each result should be printed on a new line.
Example:
Input:
1
4
2 3 4 5
3 4 5 6
5
Output:
7
Explanation:
In the given test case, the thief can carry items with weight 2 and 3 for a total value of 3 + 4 = 7, which is the maximum possible value without exceeding the capacity W=5.
Constraints:
1 <= T <= 10
1 <= N <= 10^2
1 <= wi <= 50
1 <= vi <= 10^2
1 <= W <= 10^3
- Time Limit: 1 second
Note:
Can this problem be solved with a space complexity of no more than O(W)
?
Yes, the 0-1 Knapsack Problem can be solved using dynamic programming with a space complexity of O(W).
Use dynamic programming to create a 2D array to store the maximum value that can be attained at ea...read more
Top Delhivery Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Reviews
Interviews
Salaries
Users/Month