Created
December 24, 2018 22:48
-
-
Save WilliamVelazquez/52ae241dfe929e356b167cbf1af1cb9a to your computer and use it in GitHub Desktop.
Algorithm that finds the combination of boxes with the greatest amount of money and that does not exceed the max capacity indicated.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*@author William*/ | |
//package challenge; | |
public class Box { | |
// Definition of tthe Box variables | |
public String name; | |
public int value; | |
public int weight; | |
public Box(String name, int value, int weight) { | |
this.name = name; | |
this.value = value; | |
this.weight = weight; | |
} | |
public String str() { | |
return name + " [value = " + value + ", weight = " + weight + "]"; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*@author William*/ | |
//package challenge; | |
import java.util.ArrayList; | |
import java.util.List; | |
public class Problem { | |
// Definition of boxes and capacity of the bag variables | |
private Box[] boxes; | |
private int capacity; | |
public Problem(Box[] boxes, int capacity) { | |
this.boxes = boxes; | |
this.capacity = capacity; | |
} | |
public Solution solve() { | |
// Definition of the Box Quantity constant | |
int BOX_QUANTITY = boxes.length; | |
// Store the max value at each box | |
int[][] matrix = new int[BOX_QUANTITY + 1][capacity + 1]; | |
// Initialized to 0 | |
for (int i = 0; i <= capacity; i++) | |
matrix[0][i] = 0; | |
// Iterate on the boxes | |
for (int i = 1; i <= BOX_QUANTITY; i++) { | |
// Iterate on each capacity | |
for (int j = 0; j <= capacity; j++) { | |
if (boxes[i - 1].weight > j) | |
matrix[i][j] = matrix[i-1][j]; | |
else | |
// Maximize value | |
matrix[i][j] = Math.max(matrix[i-1][j], matrix[i-1][j - boxes[i-1].weight] + boxes[i-1].value); | |
} | |
} | |
int res = matrix[BOX_QUANTITY][capacity]; | |
int w = capacity; | |
List<Box> itemsSolution = new ArrayList<>(); | |
for (int i = BOX_QUANTITY; i > 0 && res > 0; i--) { | |
if (res != matrix[i-1][w]) { | |
itemsSolution.add(boxes[i-1]); | |
// Remove boxes value and weight | |
res -= boxes[i-1].value; | |
w -= boxes[i-1].weight; | |
} | |
} | |
return new Solution(itemsSolution, matrix[BOX_QUANTITY][capacity]); | |
} | |
public static void main(String[] args) { | |
int MAX_CAPACITY = 150; | |
Box[] boxes = { | |
new Box("BoxA", 100, 40), | |
new Box("BoxB", 20, 10), | |
new Box("BoxC", 40, 120), | |
new Box("BoxD", 20, 20), | |
new Box("BoxE", 10, 10) | |
}; | |
Problem challenge = new Problem(boxes, MAX_CAPACITY); | |
Solution solution = challenge.solve(); | |
solution.showResult(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*@author William*/ | |
//package challenge; | |
import java.util.List; | |
public class Solution { | |
// Definition of the list of boxes to put in the bag and the maximal value variables | |
public List<Box> boxes; | |
public int value; | |
public Solution(List<Box> boxes, int value) { | |
this.boxes = boxes; | |
this.value = value; | |
} | |
public void showResult() { | |
if (boxes != null && !boxes.isEmpty()){ | |
System.out.println("**** Solution ****"); | |
System.out.println("Max capacity = " + value); | |
System.out.println("Box to pick:"); | |
for (Box box : boxes) { | |
System.out.println("--> " + box.str()); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Test Output
Inputs:
BoxA: $100 usd, 40kg
BoxB: $20 usd, 10kg
BoxC: $40 usd, 120kg
BoxD : $20 usd, 20kg
BoxE: $10 usd, 10kg
Max capacity: 150kg