top of page
Caută
Poza scriitoruluioanaunciuleanu

Knapsack Problem in JAVA

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.

4 afișări0 comentarii

Postări recente

Afișează-le pe toate

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Comments


bottom of page