Pengaplikasian algoritma C++ untuk menyelesaikan 0/1 Knapsack Problem

Permasalahan Knapsack untuk Algoritma Greedy dapat diselesaikan dengan menggunakan program. Pada makalah ini untuk melakukan perhitungan knapsack problem digunakan c++ sebagai tools pengaplikasiannya. Berikut adalah source code untuk menyelesaikan knapsack problem. 

// CPP code for Dynamic Programming based

// solution for 0-1 Knapsack problem

#include <bits/stdc++.h>

#include <iostream>

using namespace std;

// A utility function that returns maximum of two integers

int max(int a, int b) { 

return (a > b) ? a : b; 

}

// Prints the items which are put in a knapsack of capacity W

// Profit (Pi) = val

// Weight (Wi) = wt

// Jumlah Kapasitas = W

// CHAIRANI NADILA

void printknapSack(int W, int wt[], int val[], int n)

{

int i, w;

int K[n + 1][W + 1];

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++) {

for (w = 0; w <= W; w++) 

{

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i - 1] <= w)

K[i][w] = max(val[i - 1] +

K[i - 1][w - wt[i - 1]], K[i - 1][w]);

else

K[i][w] = K[i - 1][w];

}

}

// stores the result of Knapsack

int res = K[n][W];

cout<< "Total Keuntungan : "<<res<<endl;

w = W;

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

// either the result comes from the top

// (K[i-1][w]) or from (val[i-1] + K[i-1]

// [w-wt[i-1]]) as in Knapsack table. If

// it comes from the latter one/ it means

// the item is included.

if (res == K[i - 1][w])

continue;

else {

// This item is included.

cout<<" - Bobot : "<<wt[i - 1] ;

// Since this weight is included its

// value is deducted

res = res - val[i - 1];

w = w - wt[i - 1];

}

}

}

// CHAIRANI NADILA

// Driver code

int main()

{

cout << "Masukkan Jumlah Item dalam sebuah Knapsack : ";

int n, W;

cin >> n;

cout<<endl;

int val[n], wt[n];

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

{

cout << "Masukkan Nilai Profit (Pi) barang ke-" << i << " : ";

cin >> val[i];

cout << "Masukkan Nilai Berat  (Wi) barang ke-" << i << " : ";

cin >> wt[i];

}

cout<<endl;

cout << "Masukkan Kapasitas Knapsack : ";

cin >> W;

        cout <<endl;

printknapSack(W, wt, val, n);

    

return 0;

}

HASIL KELUARAN (OUTPUT)

PENJELASAN

Karena knapsack problem merupakan permasalahan penempatan item (barang) ke dalam suatu tempat (knapsack) yang mempunyai kapasitas tertentu. Maka setiap item tentunya memiliki berat dan nilai, sehingga total berat dari item-item yang ditempatkan tidak melebihi kapasitas tempat dan nilai yang didapatkan maksimum.

Pada contoh program, kita memiliki 4 item (barang) dengan total kapasitas Knapsack sebesar 16, dengan masing-masing nilai Pi {12,15,50,10) dan berat Wi {6,5,10,5}. Artinya terdapat 2 item (barang) yang bobotnya kurang dari atau sama dengan 16. Jika memasukkan barang dengan bobot 10 dan 6 maka nilai yang didapatkan adalah 62. Namun jika memasukkan barang dengan berat (bobot) 10 dan 5 maka nilai yang didapatkan adalah 65.

Jadi, dapat disimpulkan bahwa barang ke 2 dan 3 dapat masuk ke dalam ransel yang hanya berkapasitas 16, dengan keuntungan maksimal sebesar 65. 

REFERENSI

Printing items in 0/1 Knapsack (2022) GeeksforGeeks. Available at: https://www.geeksforgeeks.org/printing-items-01-knapsack/?ref=lbp

C program to solve Knapsack problem using dynamic programming (no date) C Program to Solve Knapsack Problem Using Dynamic Programming. Available at: https://www.tutorialspoint.com/cplusplus-program-to-solve-knapsack-problem-using-dynamic-programming