0/1 Knapsack
Medium · Dynamic Programming · about 20 minutes
Asked at Amazon, Google, Microsoft.
You have items with weights[i] and values[i] and a bag with capacity capacity. Each item can be taken at most once. Return the maximum total value of items whose total weight is at most capacity.