Skip to content

Instantly share code, notes, and snippets.

@WilliamVelazquez
Created December 24, 2018 22:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save WilliamVelazquez/52ae241dfe929e356b167cbf1af1cb9a to your computer and use it in GitHub Desktop.
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.
/*@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 + "]";
}
}
/*@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();
}
}
/*@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());
}
}
}
}
@WilliamVelazquez
Copy link
Author

WilliamVelazquez commented Dec 24, 2018

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

screenshot_4318

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment