Question

1. Consider the knapsack problem with the capacity C = 8 and 5 items with weights 6, 4, 3, 7, 1. Find which items will exactly fill the knapsack using dynamic programming solution introduced in class. Show all your work. use I/O knapsack

Answer 1

Answer:

There has to be some values (prices as such) of the given items. I have given some random values of the items to solve the knapsack problem.

Code:

import java.util.ArrayList;

import java.util.List;

class Item {

    public String name;

    public int value;

    public int weight;

    public Item(String name,int value,int weight){

        this.name=name;

        this.value=value;

        this.weight=weight;

    }

    public String str(){

        return name + "[value = " + value  + ", weight = " + weight + "]";

    }

}

class Solution{

    public List<Item> items;

    public int value;

    public Solution(List<Item> items,int value){

        this.items=items;

        this.value=value;

    }

    public void display(){

        if(items!=null && !items.isEmpty()){

            System.out.println("\n Knapsack problem");

            System.out.println("Value: "+value);

            System.out.println("Items to pick:");

            for(Item item:items){

                System.out.println("- "+item.str());

            }

        }

    }

}

public class Knapsack{

    private Item[] items;

    private int capacity;

    public Knapsack(Item[] items,int capacity){

        this.items=items;

        this.capacity=capacity;

    }

    public void display(){

        if(items!=null && items.length>0){

            System.out.println("Knapsack problem");

            System.out.println("Capacity: "+capacity);

            System.out.println("Items:");

            for(Item item:items){

                System.out.println("- "+item.str());

            }

        }

    }

    public Solution solve(){

        int NB_ITEMS=items.length;

        int[][] matrix=new int[NB_ITEMS+1][capacity+1];

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

            matrix[0][i]=0;

        for(int i=1;i<=NB_ITEMS;i++){

            for(int j=0;j<=capacity;j++){

                if(items[i-1].weight>j){

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

                }

                else{

                    matrix[i][j]=Math.max(matrix[i-1][j],matrix[i-1][j-items[i-1].weight]+items[i-1].value);

                }

            }

        }

        int res=matrix[NB_ITEMS][capacity];

        int w=capacity;

        List<Item> itemsSolution=new ArrayList<>();

        for(int i=NB_ITEMS;i>0 && res>0;i--){

            if(res!=matrix[i-1][w]){

                itemsSolution.add(items[i-1]);

                res-=items[i-1].value;

                w-=items[i-1].weight;

            }

        }

        return new Solution(itemsSolution,matrix[NB_ITEMS][capacity]);

    }

    public static void main(String[] args){

        Item[] items={new Item("Elt1",4,6),new Item("Elt2",2,4),new Item("Elt3",2,3),new Item("Elt4",1,7),new Item("Elt5",10,1)};

        Knapsack knapsack=new Knapsack(items,8);

        knapsack.display();

        Solution solution=knapsack.solve();

        solution.display();

    }

}

Output: