use this code template to help you continue:
use this code template to help you continue:
private boolean included
Indicates whether the item should be taken or not
public Item(String name, double weight, int value)
Initializes the Item’s fields to the values that are passed in; the included Field is initialized to false
public Item(Item other)
Initializes this item’s fields to the be the same as the other item’s
public void setIncluded(boolean included)
Setter for the item’s included field (you don’t need setters for the other fields)
Given code:
public class Item {
private final String name;
private final double weight;
private final int value;
private boolean included;
public Item(String name, double weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public Item(Item item){
name = item.name;
weight = item.weight;
value = item.value;
}
public void setInclude(boolean included){
this.included = included;
}
public boolean getInclude(){ return included; }
static int max(int a, int b)
{
if(a > b)
return a;
return b;
}
// function to print the items which are taken
static void printSelection(int W, Item[] items, int size)
{
int index, w;
int table[][] = new int[size + 1][W + 1];
for (index = 0; index <= size; index++) {
for (w = 0; w <= W; w++) {
// if weight is 0, the table[index][w] = 0
if (index == 0 || w == 0)
table[index][w] = 0;
// check if weight of item at index is less that w
else if (items[index - 1].weight <= w) {
// we can either include the item in the solution and subtract its weight from w
// or we can not include the item
// select, the maximum of two scenarios
table[index][w] = Math.max(items[index - 1].value + table[index - 1][(int) (w - items[index - 1].weight)], table[index - 1][w]);
}
else
table[index][w] = table[index - 1][w];
}
}
// store the result of total selling value
int result = table[size][W];
System.out.println("The total selling price will be worth $" + result);
w = W;
System.out.println("\nThe items are: ");
for (index = size; index > 0 && result > 0; index--) {
if (result == table[index - 1][w])
continue;
else {
// print the item that is included
System.out.print(items[index - 1].name + "\n");
// since weight of this item is taken
// we subtract it from total weight => result
result = result - items[index - 1].value;
w = (int) (w - items[index - 1].weight);
}
}
}
public static void main(String[] args) {
Item[] items = new Item[7];
// we are solving this problem by DP, which uses integer value
// so we are multiplying each weight by 100 and storing the weight
// hence, 0.25 become 0.25 * 100 = 25 and so on.....
items[0] = new Item("Cell phone", 25, 600);
items[1] = new Item("Gaming laptop", 1000, 2000);
items[2] = new Item("Jewelry", 50, 500);
items[3] = new Item("Kindle", 50, 300);
items[4] = new Item("Video game console", 300, 500);
items[5] = new Item("Small cuckoo clock", 500, 1500);
items[6] = new Item("Silver paperweight", 200, 400);
int index = 4;
Item new_item = new Item(items[2]);
items[index].setInclude(false);
Item[] new_items_array = new Item[items.length];
// System.out.println("Items arr len: "+items.length);
boolean check_flag = true;
if(!items[index].getInclude()){
for(int i=0;i<items.length;i++){
if(i==index && check_flag==true){
i--;
check_flag = false;
continue;
}
new_items_array[i] = items[i];
}
new_items_array[new_items_array.length - 1] = new_item;
}
// for(Item x:new_items_array){
// System.out.println(x);
// }
// System.out.println("Items new arr len: "+new_items_array.length);
// since we are multiplying each weight by 100, hence the bag value is also multiplied by 10
// Thus, 10 become 1000
int W = 1000;
int n = new_items_array.length;
printSelection(W, new_items_array, n);
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 5 images