Knapsack Problem

Knapsack problem merupakan masalah optimasi pemilihan item. Diberikan sejumlah item yang memiliki berat (weight) dan nilai (value) serta sebuah tas penampung (knapsack) yang memiliki batasan kapasitas (limit). Knapsack problem merupakan problem bagaimana memilih kombinasi item yang tepat untuk dimasukkan ke dalam knapsack agar total value dari item-item yang dimasukkan bisa maksimum dan total weight dari item-item tersebut kurang atau sama dengan limit.

Problem ini biasanya diilustrasikan dengan seorang pencuri yang masuk ke dalam suatu rumah yang akan ia curi. Di dalam rumah itu si pencuri menemui beberapa barang yang bisa ia curi diantaranya cincin berlian, televisi, radio, hp, laptop, dan kipas angin. Si Pencuri hanya mempunyai sebuah tas ransel yang kapasitasnya terbatas untuk menampung barang curiannya. Masing-masing barang memiliki berat dan nilai masing-masing, dan pencuri tidak dapat membawa semua barang tersebut. Barang-barang apa saja yang sebaiknya diambil si pencuri agar barang yang dicurinya memiliki nilai total maksimum jika kapasitas tas ransel si pencuri terbatas???

Untuk membantu si pencuri (memecahkan Knapsack Problem) bisa dengan menggunakan Dynamic Programming.

Misal kita memiliki sejumlah barang dengan jumlah n. Barang-barang itu membutuhkan array of value v{}, weight w{} dan limit kapasitas knapsack adalah max. Kemudian kita buat array dua dimensi knap{n+1,max+1}. Kita isi array dengan ketentuan sbb:

• knap{i,j} = -~ (negatif tak hingga) jika j < 0.
• knap{i,j} = 0 untuk i = 0. Karena untuk barang yang tidak ada maka tidak perlu dianalisa.
• knap{i,j} = 0 untuk j = 0. Karena untuk knapsack dengan kapasitas kosong berarti tidak ada barang.
• knap{i,j} = max(knap{i-1,j},vi+knap{i-1,j-wi}), untuk vi adalah value item pada saat i dan wi adalah weight item pada saat i

Hasil algoritma:

• Total value maksimum dari kombinasi barang adalah knap{n,max}.
• Kombinasi barang untuk jumlah value maksimum dicari melalui back tracking.

Source Code Java

Class Knapsack:

package knapsackproblem;

/**
 *
 * @author Nur Dian Wahyu S
 */
public class Knapsack {

    int n;                          // number of item
    int wMax;                       // max kapacity of knapsack
    private int[] value;            // save item value
    private int[] weight;           // save item weight
    private int[][] data;           // store data manipulated to solve problem
    private int[][] solution;       // array to find item combination
    private boolean[] take;         // store item combination

    public Knapsack(int a, int b)
    {
        this.n = a;
        this.wMax = b;

        init();
    }

    public void init()
    {
        value = new int[n+1];
        weight = new int[n+1];

        int v,w;
        for(int i=1; i<=n; i++)
        {
            do{
                v = (int) (Math.random()*10);   // value is set random
                w = (int) (Math.random()*10);   // weight is set random
                value[i] = v;
                weight[i] = w;
            }while(v==0||w==0);
        }

        data = new int[n+1][wMax+1];
        solution = new int[n+1][wMax+1];

        // set data value on [0][0...max] to "0"
        for(int x=0; x<=wMax; x++)
            data[0][x] = 0;
        // set data value on [0...n][0] to "0"
        for(int x=0; x<=n; x++)
            data[x][0] = 0;

        // solution of knapsack problem
        for(int i=1; i<=n; i++)
            for(int j=0; j<=wMax; j++)
            {
                int option1 = data[i-1][j];
                int option2 = -1000000;
                if(j-weight[i]>=0)
                    option2 = value[i]+data[i-1][j-weight[i]];

                data[i][j] = Math.max(option1, option2);
                if(option2 > option1)       // solution is initialized by "1"
                    solution[i][j] = 1;     // to find the combination item later
            }

        take = new boolean[n+1];
        int j = wMax;
        for(int i=n; i>0; i--)
        {
            if(solution[i][j]==1)
            {
                take[i] = true;
                j = j-weight[i];
            }
            else
                take[i] = false;
        }
    }

    public void printItem()
    {
        System.out.print("Items Value  : ");
        for(int i=1; i<=n; i++)
            System.out.print(value[i]+" ");
        System.out.println();
        System.out.print("Items Weight : ");
        for(int i=1; i<=n; i++)
            System.out.print(weight[i]+" ");
        System.out.println("\n");
    }

    public void printSolution()
    {
        System.out.println("Array solution of knapsack problem");
        for(int i=0; i<=n; i++)
        {
            for(int j=0; j<=wMax; j++)
            {
                System.out.print(data[i][j]+" ");
            }
            System.out.println();
        }

        System.out.println("\nResult solution of knapsack problem");
        System.out.println("ITEM"+"     "+"VALUE"+"    "+"WEIGHT"+"   "+"TAKE");
        for(int i=1; i<=n; i++)
        {
            System.out.println(i+"\t"+value[i]+"\t"+weight[i]+"\t"+take[i]);
        }

        System.out.println("The best of total value to be taken is "+data[n][wMax]);
    }
}

Class Main:

package knapsackproblem;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @author Nur Dian Wahyu S
 */
public class Main {

    public static void main(String[] args) throws IOException {
        
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("KNAPSACK PROBLEM");
        System.out.print("Total Items: ");
        String item = input.readLine();
        int nItem = Integer.parseInt(item);
        System.out.print("Knapsack Maximum capacity: ");
        String cap = input.readLine();
        int Max = Integer.parseInt(cap);
        System.out.println();
        
        Knapsack k = new Knapsack(nItem,Max);
        k.printItem();
        k.printSolution();
    }

}

Screenshot: