Long term reader, first time poster. I've been banging my head against this problem for a few months now and I'm starting to wave the white flag here.
Problem: Set a lower bound on the number of items stuffed into a knapsack in the knapsack problem.
The Knapsack Problem is a well known problem of combinatorial optimization. Given a set of items, each with a weight and a value, we must determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value must be maximized. (https://ssaurel.medium.com/solving-the-knapsack-problem-in-java-c985c71a7e64)
The algorithm I'm utilizing is the DP dynamic programming flavor, and current guidance says in order to set a bound on the number of items selected, you add another dimension to the dp[] array. I successfully implemented this for an upper bound (ie maximum number of items that can be selected), but darned if I can get the lower bound to work. I also tried tinkering with the integer range in the for loop used to control the upper bound with no success.
In my data input, I have 4 items: RUBY, DIAMOND, EMERALD, SAPPHIRE. In the program below I overweight the RUBY's value so the knapsack can only store the 1 item; however, the desired behavior is to accept the minItems constraint so the RUBY would be discounted and the other gems selected as part of the solution. (Desired output below). Lil help? Thanks in advance.
KL
public class Knapsack {
static class Item {
private int weight;
private int value;
private String name;
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public static void main(String[] args) {
int[][][] dp = null;
int weightLimit = 100;
int maxItems = 3; //Works by adding a 3rd dimension to the dp array
int minItems = 3; // ------------> Can't get working. Bah!
//The list of items from which you select to pack into your knapsack
ArrayList<Item> itemList = new ArrayList<Item>();
//Create some items and add them to a list
//The RUBY is given the highest value and also highest weight, which nearly stuffs the whole knapsack. It is selected
//by the algorithm as providing the best value, however, if a minimumNumber of items is specified, I want it to discount
//that solution and select the DIAMOND, EMERALD, AND SAPPHIRE instead. The max uppper bound seems to work just fine....
Item item1 = new Item();
item1.setName("RUBY");
item1.setValue(90);
item1.setWeight(110);
itemList.add(item1);
Item item2 = new Item();
item2.setName("DIAMOND");
item2.setValue(15);
item2.setWeight(15);
itemList.add(item2);
Item item3 = new Item();
item3.setName("EMERALD");
item3.setValue(10);
item3.setWeight(15);
itemList.add(item3);
Item item4 = new Item();
item4.setName("SAPPHIRE");
item4.setValue(10);
item4.setWeight(15);
itemList.add(item4);
//Dynamic Programming Knapsack solution as per everywhere on the internet (https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/)
Item[] items = itemList.toArray(new Item[itemList.size()]);
ArrayList<Item> selectedList = new ArrayList<Item>();
int numItems = itemList.size();
dp = new int[numItems + 1][weightLimit + 1][maxItems + 1];
// for each item
for (int i = 1; i <= numItems; i++) {
// For each possible weight
for (int j = 1; j <= weightLimit; j++) {
// For each case where the total items are less than the maximum allowed ----------------------------> Adding this 3rd dimension to the dp array ensures we can set a maximum number of items to select
for (int k = 1; k <= maxItems; k++) {
// To ensure that we dont go out of the array
if (j >= items[i - 1].getWeight()) {
dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - items[i - 1].getWeight()][k - 1] + items[i - 1].getValue());
} else {
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
int res = dp[numItems][weightLimit][maxItems];
int j = weightLimit;
int k = maxItems;
for (int i = numItems; i > 0 && res > 0; i--) {
// either the result comes from the top
// (K[i-1][w]) or from (val[i-1] + K[i-1]
// [w-wt[i-1]]) as in Knapsack table. If
// it comes from the latter one/ it means
// the item is included.
if (res == dp[i - 1][j][k])
continue;
else {
// This item is included.
selectedList.add(items[i-1]);
// Since this weight is included its value is deducted
res = res - items[i - 1].getValue();
j = j - items[i - 1].getWeight();
k = k - 1;
}
}
//print out the list of selected items
System.out.println("Knapsack contents:");
for (Item item : selectedList) {
System.out.println("Item: " + item.getName() + " Value:" + item.getValue() + " Weight: " + item.getWeight());
}
}
}
Current Output:
Item: RUBY Value:90 Weight90
Desired Output:
Item: SAPPHIRE Value:10 Weight15
Item: EMERALD Value:10 Weight15
Item: DIAMOND Value:15 Weight15