You must introduce values into a knapsack. With n items given with weights and values, return the maximum sum of values of the subset such that the sum of weights of items is smaller or equal to the capacity of the knapsack.
Input: int values[] = {60, 100, 120}; int weights[] = {10, 20, 30}; int capacity = 50; Output: 220 Explanation: All the possible combinations are: Weight = 10; Value = 60; Weight = 20; Value = 100; Weight = 30; Value = 120; Weight = (20 + 10); Value = (100 + 60); Weight = (30 + 10); Value = (120 + 60); Weight = (30 + 20); Value = (120 + 100); Weight = (30 + 20 + 10) > 50; The larger value is 220. |
Solution:
1. static int knapsack(int capacity, int[] weights, int[] values) { 2. int valuesSize = values.length; 3. int[] solutions = new int[capacity + 1]; 4. 5. for (int i = 1; i < valuesSize + 1; i++) { 6. for (int j = capacity; j >= 0; j--) { 7. if (weights[i - 1] <= j) { 8. solutions[j] = Math.max(solutions[j], 9. solutions[j - weights[i - 1]] + values[i - 1]); 10. } 11. } 12. } 13. return solutions[capacity]; 14. } 15.