Reputation: 557
I've a problem similar to the 0-1 Knapsack.
The modification I'm trying to do is to get the list of selected object instead of cost. I tried with the following code:
public static int fillPackage(double weight,ArrayList<Item> item, int n) {
//base case
if(n == 0 || weight == 0)
return 0;
if(item.get(n - 1).getWeight() > weight)
return fillPackage(weight, item, n - 1);
else {
int include_cost = item.get(n - 1).getCost() + fillPackage((weight - item.get(n - 1).getWeight()), item, n - 1);
int exclude_cost = fillPackage(weight, item, n - 1);
if(include_cost > exclude_cost) {
my_pack.add(item.get(n - 1));
return include_cost;
}
else {
return exclude_cost;
}
}
}
Here my_pack
is the ArrayList
that is supposed to store the selected object.
But, it is storing other objects too. Also, I can't use DP table method because my parameters are float
.
Where should my_pack.add()
line be put ?
Upvotes: 3
Views: 2324
Reputation: 7530
Q:
where should
my_pack.add()
line be put ?
A:
Put my_pack.add()
to nowhere to get right code.
Let me tell you how to do it. You know the way to solve 0-1 Knapsack
is:
best_cost = max(included_cost, excluded_cost)
So similarly, you should think your problem in this way:
if included_cost > excluded_cost
best_choice = included_best_choice + included_item
else
best_choice = excluded_best_choice
I modified your code and it can solve your problem correctly(you can edit and run my test code). See my code below.
If you have any question, feel free to leave a comment and I will reply as soon as possible.
import java.util.ArrayList;
import java.util.List;
public class Package {
static List<Item> my_pack;
public static int fillPackage(double weight, ArrayList<Item> item, List<Item> optimalChoice, int n){
//base case
if(n == 0 || weight == 0)
return 0;
if(item.get(n-1).getWeight() > weight) {
List<Item> subOptimalChoice = new ArrayList<>();
int optimalCost =fillPackage(weight, item, subOptimalChoice, n-1);
optimalChoice.addAll(subOptimalChoice);
return optimalCost;
}
else{
List<Item> includeOptimalChoice = new ArrayList<>();
List<Item> excludeOptimalChoice = new ArrayList<>();
int include_cost = item.get(n-1).getCost() + fillPackage((weight-item.get(n-1).getWeight()), item, includeOptimalChoice, n-1);
int exclude_cost = fillPackage(weight, item, excludeOptimalChoice, n-1);
if(include_cost > exclude_cost){
optimalChoice.addAll(includeOptimalChoice);
optimalChoice.add(item.get(n - 1));
return include_cost;
}
else{
optimalChoice.addAll(excludeOptimalChoice);
return exclude_cost;
}
}
}
public static void main(String args[]) {
ArrayList<Item> itemList = new ArrayList<>();
itemList.add(new Item(2, 1));
itemList.add(new Item(5, 6));
itemList.add(new Item(3, 2));
itemList.add(new Item(4, 4));
itemList.add(new Item(7, 7));
printOptimalChoice(itemList, 9);
printOptimalChoice(itemList, 10);
printOptimalChoice(itemList, 11);
}
private static void printOptimalChoice(ArrayList<Item> itemList, double weight) {
my_pack = new ArrayList<>();
fillPackage(weight, itemList, my_pack, itemList.size());
System.out.println("Best choice for weight: " + weight);
for(int i = 0; i < my_pack.size(); i++) {
System.out.println(my_pack.get(i));
}
}
}
My test output:
Best choice for weight: 9.0
Item{weight=5.0, cost=6}
Item{weight=4.0, cost=4}
Best choice for weight: 10.0
Item{weight=5.0, cost=6}
Item{weight=4.0, cost=4}
Best choice for weight: 11.0
Item{weight=2.0, cost=1}
Item{weight=5.0, cost=6}
Item{weight=4.0, cost=4}
code of Item.class
:
class Item {
private double weight;
private int cost;
public Item(double weight, int cost) {
this.weight = weight;
this.cost = cost;
}
@Override
public String toString() {
return "Item{" +
"weight=" + weight +
", cost=" + cost +
'}';
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;
}
}
Upvotes: 6