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

Question

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 ", bestWeight, bestValue);
        System.out.printf("Number of valid knapsack's: %d ", 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

Explanation / Answer

Dynamic Programming:
Create a 2D array with number of rows as items and columns equal to capacity

Let arr[i][j] denote the value of array at ith row and jth column
arr[i][j] means what is the maximum value we can get if we use only first i items and have a capacity of j.
arr[i][j] = max(arr[i-1][j], arr[i][j-1], arr[i-1][j-weight[i]])

Complexity of Algorithm :
It is equal to time required to create the 2d array = Size of Array

Big O Notation : O(capacity*number of items) = O(n*capacity)

********************************************************

import java.util.*;

class Main {
  
    public static void main(String args[] ) throws Exception {
       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 capacity = 20; // Max pounds that can be carried
        int n = 16; // number of items in the store
      
        // 2d array with rows as items and columns as maximum capacity
        int arr[][] = new int[n][capacity+1];
      
        // Calculating the maximum Value
        for (int i = 1; i <n; i++) {
           for (int j = 1; j <= capacity; j++) {
               arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j]);
               if (j - weights[i] >=0){ // as putting the current items in knapsack possible
                   arr[i][j] = Math.max(arr[i][j] , arr[i-1][j-weights[i]] + values[i]);
               }
           }
       }
        System.out.println("Maximum Value : "+arr[n-1][capacity]);
      
        // Calculating the Weight of Knapsack to achieve the Maximum Value
        int sumWeight = 0;
        int i = n-1, j = capacity;
        while (i>0 && j>0){
           if (arr[i][j] == arr[i-1][j]){
               i = i-1;
           } else if (arr[i][j] == arr[i][j-1]){
               j = j -1;
           } else {
               sumWeight += weights[i];
               j= j- weights[i];
               i--;
           }
        }
      
        System.out.println("Total Knapsack Weight : "+sumWeight);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.