use this code template to help you continue:

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

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;

 

    public Item(String name, double weight, int value) {
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

 

    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);

 

        // 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 = items.length;
 
        printSelection(W, items, n);
    }
}
File
Home
Insert
Draw
Design
Layout
References
Mailings
Review
View
Help
RCM
Comments
A Share
E - E - E
Times New Roman
12
A A Aa v
Normal
No Spacing
Heading 1
Editing
Paste
в IU
ab X2
x A
A
Dictate
Sensitivity
Editor
Reuse
Files
Undo
Clipboard
Font
Paragraph
Styles
Voice
Sensitivity
Editor
Reuse Files
In java:
Based on the concept of natural selection. They allow
a set of solutions to a problem that score well against a fitness function. An example is
particularly helpful in understanding this concept. We'll use the bin packing problem, which is a
famous problem in computer science. Pretend that your town is being attacked by zombies, and
you have to abandon your house and go on the run. (It's possible that this isn't *exactly* how the
problem is classically described, but this version is way more interesting.) You are only able to
carry 10 pounds of stuff with you in addition to food and other necessities, and you want to bring
things that you can sell for the greatest amount of money possible. Below is a list of items you
could take, along with their weight and selling price. Which items should you take with you in
order to maximize the amount of money you can get?
to explore a search space by “evolving"
Item,weight,worth
Cell phone, 0.25, 600
Gaming laptop, 10, 2000
Jewelry, 0.5, 500
Kindle, 0.5, 300
Video game console, 3, 500
Small cuckoo clock, 5, 1500
Silver paperweight, 2, 400
It turns out that the best you can do in this situation is to take the cell phone, jewelry, Kindle,
video game console, and small cuckoo clock. Together, these items weigh 9.25 pounds and are
worth $3400. The tricky thing about the bin packing problem is that the only way you can be
sure that you have the optimal set of items is to try all possible combinations. You might be
tempted to try short cuts, like taking items in order of worth until you hit the weight limit (which
in this case would mean taking just the gaming laptop, worth $2000) or taking the lightest items
until
reach the weight limit (which in this case would be the cell phone, jewelry, Kindle,
you
silver paperweight, and video game console, worth $2300). Neither of these strategies nets as
much money as the optimal combination. Trying all possible combinations is a lot of work, and
the zombies might get you while you're trying to work things out. The solution we end up with is
not guaranteed to be the optimal one, but it is likely to at least be pretty good.
Tou
<> 1>
>
Transcribed Image Text:File Home Insert Draw Design Layout References Mailings Review View Help RCM Comments A Share E - E - E Times New Roman 12 A A Aa v Normal No Spacing Heading 1 Editing Paste в IU ab X2 x A A Dictate Sensitivity Editor Reuse Files Undo Clipboard Font Paragraph Styles Voice Sensitivity Editor Reuse Files In java: Based on the concept of natural selection. They allow a set of solutions to a problem that score well against a fitness function. An example is particularly helpful in understanding this concept. We'll use the bin packing problem, which is a famous problem in computer science. Pretend that your town is being attacked by zombies, and you have to abandon your house and go on the run. (It's possible that this isn't *exactly* how the problem is classically described, but this version is way more interesting.) You are only able to carry 10 pounds of stuff with you in addition to food and other necessities, and you want to bring things that you can sell for the greatest amount of money possible. Below is a list of items you could take, along with their weight and selling price. Which items should you take with you in order to maximize the amount of money you can get? to explore a search space by “evolving" Item,weight,worth Cell phone, 0.25, 600 Gaming laptop, 10, 2000 Jewelry, 0.5, 500 Kindle, 0.5, 300 Video game console, 3, 500 Small cuckoo clock, 5, 1500 Silver paperweight, 2, 400 It turns out that the best you can do in this situation is to take the cell phone, jewelry, Kindle, video game console, and small cuckoo clock. Together, these items weigh 9.25 pounds and are worth $3400. The tricky thing about the bin packing problem is that the only way you can be sure that you have the optimal set of items is to try all possible combinations. You might be tempted to try short cuts, like taking items in order of worth until you hit the weight limit (which in this case would mean taking just the gaming laptop, worth $2000) or taking the lightest items until reach the weight limit (which in this case would be the cell phone, jewelry, Kindle, you silver paperweight, and video game console, worth $2300). Neither of these strategies nets as much money as the optimal combination. Trying all possible combinations is a lot of work, and the zombies might get you while you're trying to work things out. The solution we end up with is not guaranteed to be the optimal one, but it is likely to at least be pretty good. Tou <> 1> >
Expert Solution
SOURCE 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

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 5 images

Blurred answer
Knowledge Booster
Introduction to Template
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education