Question

In: Computer Science

A thief robbing a store can carry a maximum weight of W in their knapsack. There...

A thief robbing a store can carry a maximum weight of W in their knapsack. There are n items and ith item weighs wi and is worth vi dollars. What items should the thief take to maximize the value of what is stolen?

The thief must adhere to the 0-1 binary rule which states that only whole items can be taken. The thief is not allowed to take a fraction of an item (such as ½ of a necklace or ¼ of a diamond ring). The thief must decide to either take or leave each item.

Develop an algorithm using Java and developed in the Cloud9 environment (or your own Java IDE) environment to solve the knapsack problem.  

Your algorithms should use the following data as input.

Maximum weight (W) that can be carried by the thief is 20 pounds

There are 16 items in the store that the thief can take (n = 16). Their values and corresponding weights are defined by the following two lists.

Item Values: 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5

Item Weights: 1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1

Your solution should be based upon dynamic programming principles as opposed to brute force.

The brute force approach would be to look at every possible combination of items that is less than or equal to 20 pounds. We know that the brute force approach will need to consider every possible combination of items which is 2n items or 65536.

The optimal solution is one that is less than or equal to 20 pounds of weight and one that has the highest value.   The following algorithm is a ‘brute force’ solution to the knapsack problem. This approach would certainly work but would potentially be very expensive in terms of processing time because it requires 2n (65536) iterations

The following is a brute force algorithm for solving this problem. It is based upon the idea that if you view the 16 items as digits in a binary number that can either be 1 (selected) or 0 (not selected) than there are 65,536 possible combinations. The algorithm will count from 0 to 65,535, convert this number into a binary representation and every digit that has a 1 will be an item selected for the knapsack. Keep in mind that not ALL combinations will be valid because only those that meet the other rule of a maximum weight of 20 pounds can be considered. The algorithm will then look at each valid knapsack and select the one with the greatest value.

import java.lang.*;
import java.io.*;

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int a, i, k, n, b, Capacity, tempWeight, tempValue, bestValue, bestWeight;
        int remainder, nDigits;
        int Weights[] = {1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};
        int Values[] = { 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };
        int A[];
      
        A = new int[16];

        Capacity = 20; // Max pounds that can be carried
        n = 16; // number of items in the store
        b=0;

        tempWeight = 0;
        tempValue = 0;
        bestWeight = 0;
        bestValue = 0;

    for ( i=0; i<65536; i++) {
                remainder = i;

                // Initialize array to all 0's
                for ( a=0; a<16; a++) {
                    A[a] = 0;
                }

                // Populate binary representation of counter i
                //nDigits = Math.ceil(Math.log(i+0.0));
                nDigits = 16;

                for ( a=0; a<nDigits; a++ ) {
                    A[a] = remainder % 2;
                    remainder = remainder / 2;
                }

                // fill knapsack based upon binary representation
                for (k = 0; k < n; k++) {

                    if ( A[k] == 1) {
                        if (tempWeight + Weights[k] <= Capacity) {
                            tempWeight = tempWeight + Weights[k];
                            tempValue = tempValue + Values[k];
                        }
                    }
                }

                // if this knapsack is better than the last one, save it
                if (tempValue > bestValue) {
                    bestValue = tempValue;
                    bestWeight = tempWeight;
                    b++;
                }
                tempWeight = 0;
                tempValue = 0;
        }
        System.out.printf("Weight: %d Value %d\n", bestWeight, bestValue);
        System.out.printf("Number of valid knapsack's: %d\n", b);
    }
}

The brute force algorithm requires 65,536 iterations (216) to run and returns the output defined below. The objective of this assignment will be to develop a java algorithm designed with dynamic programming principles that reduces the number of iterations.   The brute force algorithm requires an algorithm with exponential 2n complexity where O(2n). You must create a dynamic programming algorithm using java to solve the knapsack problem. You must run your algorithm using Java and post the results.   You results must indicate the Weight of the knapsack, the value of the contents, and the number of iterations just as illustrated in the brute force output below.   You must also include a description of the Big O complexity of your algorithm.

Output from the Brute Force Algorithm.

Weight: 20
Value: 280
Number of valid knapsack's: 45

For a hint on the dynamic programming approach see the following:

The basic idea behind the dynamic programming approach: Compute the solutions to the sub-problems once and store the solutions in a table, so that they can be reused (repeatedly) later.
http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

Some of these algorithms may take a long time to execute. If you have access to a java compiler on your local computer or the Virtual Computing Lab, you may want to test your code by running it and executing it with java directly as it can speed up the process of getting to a result. You should still execute your code within Java to get an understanding of how it executes. (To compile with java use the javac command. To run a compiled class file, use the java command)

Solutions

Expert Solution

The Knapsack problem can be solved by using Dynamic Programming. We have two input arrays:


where N is the length of arrays Weights and Values respectively. We define a new two dimensional array,

DP[ i ][ j ] denotes the maximum value the thief can get if he considers only items with 0 to i and given he can carry a maximum weight of j only.

Now, assume you know the answer of all sub problems considering items less than i and maximum weight less than j, how do you calculate DP[ i ][ j ] using those sub problems? We try to find a recursive relation.

You want to find DP[ i ][ j ], that is, maximum value using items 0 to i given maximum weight j the robber can carry. Here, to robber has two choices:

  1. Pick the ith item with value vi and weight wi. In this case, the value we get is viplus the best possible answer of all the sub problems with items to consider less than i and maximum weight to carry (j - wi). So in this case,  
  2. Leave the ithitem. In this case, because we skipped the ith item, the value we get is only the best possible answer of the sub problem with items to consider with index less than i and maximum weight to carry j. So in this case,

Now, the answer to DP[ i ][ j ] will be the maximum value from the two possible cases.

For N = 16 and Capacity = 20, the dynamic programming solution takes iterations, that is, 16 * 21 = 336. The solution has a time complexity of because of two nested loops for each item and for each weight.

I am attaching the image of source code (for reference for indentation) and also putting up to code for easier copy/paste

Output of the program:

Following is the code:

import java.io.*;

import java.math.*;

import java.lang.*;


public class Main

{

public static void main(String[] args)

{

int N = 16; // Total number of items

int Capacity = 20; // Maximum weight the robber can carry

int Weights[] = {1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};

int Values[] = { 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };

int iterations = 0; // stores the number of iterations

int DP[][] = new int[N][Capacity + 1]; // Capacity + 1 because weight can range from 0 to 20 not 0 to 19

int keep[][] = new int[N][Capacity + 1]; // keep[i][j] stores whether item i is kept in knapsack if we have capacity j

for(int i = 0; i < N; i++)

{

for(int j = 0; j <= Capacity; j++)

{

iterations++;

if(i == 0)

{

// if i = 0, then take item only if its weight is less the or equal to capacity of knapsack

DP[i][j] = (Weights[i] <= j) ? Values[i] : 0;

continue;

}

if(j == 0)

{

// if capacity of knapsack is zero, we can't pick any item.

DP[i][j] = 0;

continue;

}

// Remember the recursive relation for DP[i][j]

if(j - Weights[i] >=0 && Values[i] + DP[i - 1][j - Weights[i]] > DP[i - 1][j])

{

DP[i][j] = Values[i] + DP[i - 1][j - Weights[i]];

keep[i][j] = 1;

}

else

{

DP[i][j] = DP[i - 1][j];

keep[i][j] = 0;

}

}

}

// find the weight of subset of items picked

int bestWeight = 0;

int maxCapacity = Capacity;

for(int i = 0; i < N; i++)

{

if(keep[i][Capacity] == 1)

{

bestWeight += Weights[i];

maxCapacity -= Weights[i];

}

}

System.out.println("Weight of Knapsack = " + bestWeight);

System.out.println("Maximum value of contents = " + DP[N - 1][Capacity]);

System.out.println("Number of iterations = " + iterations);

}

}


Related Solutions

Greedy algorithms. For fractional Snapsack problem, the thief can carry at most 20 pounds. If the...
Greedy algorithms. For fractional Snapsack problem, the thief can carry at most 20 pounds. If the thief finds the following items: (22 dollars, 7 pounds), (20, dollar, 5 pounds), (50 dollars, 100 pounds), (3 dollar, 1 pounds), (20 dollars, 10 pounds) , and (5 dollars, 0.5 pounds), what should the thief choose? For the interval scheduling problem, the set of jobs (si, fi) are as follows: (3, 6), (2, 4), (5, 9) (7, 10), (0, 9), (1, 3), (9, 11),...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
Consider the following items in the Knapsack Problem: Item                weight             value &nbsp
Consider the following items in the Knapsack Problem: Item                weight             value            Knapsack capacity W = 9. 1                      3                   $6 2 4 $12 3                      2                  $10 4                      5                  $20 Determine the maximum value in the knapsack if we allow repetitions; i.e., if there are an unlimited number of each item so that more than one such item can be chosen. Find the missing value in the following linear array. P(w) is the maximum profit obtainable for a knapsack of capacity w. w-->             0       1      2       3       4       5       6       7       8       9 P(w):    0 0 10 10     20     20     30    30 40 ?   P(9)...
For bending only, determine the lightest-weight W-shape to carry a uniform dead load of 4.5 kip/ft...
For bending only, determine the lightest-weight W-shape to carry a uniform dead load of 4.5 kip/ft plus the beam self-weight and a live load of 3.5 kip/ft on a simple span of 24 ft. Consider only the limit state of yielding and use A992 steel. Design by (a) LRFD
A father (weight W = 858 N) and his daughter (weight W = 372 N) are...
A father (weight W = 858 N) and his daughter (weight W = 372 N) are spending the day at the lake. They are each sitting on a beach ball that is just submerged beneath the water (see the figure). Ignoring the weight of the air in each ball, and the volumes of their legs that are under the water, find (a) the radius of father's ball and (b) the radius of daughter's ball
A father (weight W = 849 N) and his daughter (weight W = 394 N) are...
A father (weight W = 849 N) and his daughter (weight W = 394 N) are spending the day at the lake. They are each sitting on a beach ball that is just submerged beneath the water (see the figure). Ignoring the weight of the air in each ball, and the volumes of their legs that are under the water, find (a) the radius of father's ball and (b) the radius of daughter's ball.
A certain dealer owns a warehouse that can store a maximum of 600 units of a...
A certain dealer owns a warehouse that can store a maximum of 600 units of a given commodity. He has on hand 100 units of the commodity and knows the buying and selling price for the next 5 time periods. They are: PERIOD BUYING PRICE SELLING PRICE 1 15 16 2 17 17 3 21 20 4 19 19 5 16 20 He is permitted to sell up to the amount that he has in his warehouse at the beginning...
In Houston, Texas, a common method of robbing a store involves backing a pick-up truck through...
In Houston, Texas, a common method of robbing a store involves backing a pick-up truck through the front door / windows, quickly filing the bed with merchandise and driving away. Some might say this is actually good for the economy since the store owner must spend thousands repairing the damage, which gets re-spent several times. Fifty thousand in damages might result in $150,000 or more in economic activity and so the crime benefits the economy. Others describe this as the...
What is the maximum weight that can be suspended on a 25kg poll, 3/5 from the...
What is the maximum weight that can be suspended on a 25kg poll, 3/5 from the end? The maximum tension of the 30 degree guy-wire is 1500N. Find the horizontal and vertical forces exerted on the poll by the hinge.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT