0/1 Knapsack with Benefits

Question (LI.125)

Given a backpack with size K and a list of items, each item has a size and value. We want to maximize the total value while making sure that total size is less or equal to K.

Examples

I: K = 10, size = [2, 3, 5, 7], value = [1, 5, 2, 4]
O: 9 from item2 and item4

Analysis

This is the classic knapsack with an additional objective.