pakkur.cpp

/* program to implement fractional knapsack problem using greedy programming */
#include<iostream>
using namespace std;
int main()
{
    int array[2][100], n, w, i, curw, terpakai[100], maxi = -1, harga = 0;

    cout << "==============="<<endl;
    cout << "KNAPSACK GREEDY"<<endl;
    cout << "==============="<<endl;
    cout << "> Masukkan jumlah Item    = ";
    cin >> n;
    //input max weight of knapsack
    cout << "> Masukkan berat MAX (kg) = ";
    cin >> w;
    /* array kiri berat, kanan harga */
    for (i = 0; i < n; i++)
    {
        cin >> array[0][i] >> array[1][i];
    }
    for (i = 0; i < n; i++)
    {
        terpakai[i] = 0;
    }
    curw = w;
    //perulangan sampai truk penuh
    while (curw >= 0)
    {
        maxi = -1;
        //perulangan untuk mencari max harga
        for (i = 0; i < n; i++)
        {
            if ((terpakai[i] == 0) && ((maxi == -1) || (((float) array[1][i]
                    / (float) array[0][i]) > ((float) array[1][maxi]
                    / (float) array[0][maxi]))))
            {
                maxi = i;
            }
        }
        terpakai[maxi] = 1;
        //pengurangan berat
        curw -= array[0][maxi];
        //pengurangan harga
        harga += array[1][maxi];
        if (curw >= 0)
        {
            cout << "\nBarang " << maxi + 1 << " -> Berat = " << array[0][maxi] << " -> Harga = " << array[1][maxi] << ". Sisa = " << curw;
        }
        else
        {
            cout << "\nBarang " << maxi + 1 << " -> Berat = " << (array[0][maxi] + curw) << " -> Harga = "
                    << (array[1][maxi] / array[0][maxi]) * (array[0][maxi]
                            + curw) << " -> Sebagian ditambahkan -> Sisa = 0"
                    << " -> Yang dimasukkan = " << curw + array[0][maxi];
            harga -= array[1][maxi];
            harga += ((array[1][maxi] / array[0][maxi]) * (array[0][maxi]
                    + curw));
        }
    }
    cout << "\n\n> Jumlah barang dengan berat maksimal "<<w<< " KG dapat menampung dengan total harga = Rp. " << harga << endl;
    return 0;
}