My issue
Knapsack Problem
You have a knapsack that can take upto W_{max}W
max
weight.
Given NN items, i^{th}i
th
of them having the weight W_iW
i
and value V_iV
i
.
You can pick some or all the items completely so that their weight does not exceed W_{max}W
max
.
Your task is to maximise the total value of the items you will carry in your bag.
Input Format
The first line contains two integer NN and W_{max}W
max
, denoting the total number of items and capacity of the knapsack
Next NN lines contains the description of the items.
i^{th}i
th
line contains two integers W_iW
i
and V_iV
i
, denoting the Weight and Value of the i^{th}i
th
item
Output Format
Output the maximum value you can carry while not exceeding the weight limit of the knapsack.
Constraints
2 \leq N \leq 152≤N≤15
1 \leq W_i, V_i \leq 10^91≤W
i
,V
i
≤10
9
Sample 1:
Input
Output
6 15
6 5
5 6
6 4
6 6
3 5
7 2
17
My code
import heapq
import sys
infinity = sys.maxsize
def branch_and_bound(n, wmax, items):
# Write the code here
if __name__ == "__main__":
n, wmax = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
print(branch_and_bound(n, wmax, items))
Learning course: Design and Analysis of Algorithms
Problem Link: https://www.codechef.com/learn/course/kl-daa/KLDAA2428/problems/DAA174