Implementasi Algoritma Integer Knapsack Pada Bahasa Pemrograman PHP

Knapsack Problem (KP) adalah masalah penempatan item (barang) ke dalam suatu tempat (biasa disebut Knapsack) yang mempunyai kapasitas tertentu, dimana setiap item memiliki berat dan nilai, sehingga total berat dari item-item yang ditempatkan tidak melebihi kapasitas Knapsack dan nilai yang didapatkan maksimum. {0,1}-Knapsack Problem ({0,1}-KP) adalah kasus khusus dari KP dimana setiap item hanya tersedia 1 unit, sehingga keputusannya adalah untuk memasukkan item tersebut ke dalam Knapsack (x=1) atau tidak (x=0).

Implementasi algoritma Integer Knapsack untuk mendapatkan solusi optimal dari suatu permasalahan, dengan ketentuan input terdiri dari jumlah item (n), bobot setiap item (wi), profit setiap item (pi) dan kapasitas (K) knapsack dimasukkan secara interaktif sedangkan output merupakan solusi yang dihasilkan.

Berikut source code dalam bahasa pemrograman PHP :

<?php
function KnapSack($kapasitas, $bobot, $profit, $jumlah_item)
{
    $y = array();

    for ($x = 0; $x <= $jumlah_item; ++$x)
    {
        for ($z = 0; $z <= $kapasitas; ++$z)
        {
            if ($x == 0 || $z == 0)
                $y[$x][$z] = 0;
            else if ($bobot[$x - 1] <= $z)
                $y[$x][$z] = max($profit[$x - 1] + $y[$x - 1][$z - $bobot[$x - 1]], $y[$x - 1][$z]);
            else
                $y[$x][$z] = $y[$x - 1][$z];
        }
    }

    return $y[$jumlah_item][$kapasitas];
}

$profit = array(61, 102, 123);
$bobot = array(12, 23, 34);
$kapasitas = 44;
$jumlah_item = 2;

$hasil = KnapSack($kapasitas, $bobot, $profit, $jumlah_item);

echo $hasil;
?>