Unbounded Knapsack

Problem Statement A thief wants to rob a store. He is carrying a bag of capacity W. The store has n types of items, and there is an infinite supply of each type. Each item type i has a specific weight wt[i] and a value val[i]. The thief can choose to include an item type in his knapsack or exclude it. He cannot partially take an item. The objective is to find the maximum total value of items that the thief can steal, given that he can take any single item type multiple times. Input Specification n: An integer representing the number of distinct item types. W: An integer representing the maximum capacity of the knapsack. val: An array of integers, where val[i] is the value of the i th item type. wt: An array of integers, where wt[i] is the weight of the i th item type. Output Specification An integer representing the maximum total value of items that can be put into the knapsack. Constraints 1 <= n <= 100 1 <= W <= 1000 1 <= wt[i], val[i] <= 1000 Sample Test Cases Sample Input Sample Output Explanation To achieve a value of 27 with a knapsack capacity of 10: One optimal combination is taking item type 0 (weight 2, value 5) once, and item type 1 (weight 4, value 11) twice. Total weight = (1 2) + (2 4) = 2 + 8 = 10. Total value = (1 5) + (2 11) = 5 + 22 = 27.