Knapsack.cpp

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_ITEMS 8
#define CAPACITY 15

struct Item {
    int index;
    int weight;
    int profit;
    double ratio;
};

// Fungsi cetak hasil pilihan objek secara manual
void printSelectedItems(vector<Item> &items, int capacity) {
    int totalWeight = 0, totalProfit = 0;
    cout << "\nPerhitungan Manual:\n";
    cout << "Objek\tWeight\tProfit\tRatio\tDipilih\n";

    for (int i = 0; i < items.size(); i++) {
        bool dipilih = false;
        if (totalWeight + items[i].weight <= capacity) {
            totalWeight += items[i].weight;
            totalProfit += items[i].profit; 
            dipilih = true;
        }

        cout << items[i].index + 1 << "\t"
             << items[i].weight << "\t"
             << items[i].profit << "\t"
             << fixed << setprecision(2) << items[i].ratio << "\t"
             << (dipilih ? "Ya" : "Tidak") << endl;
    }

    cout << "\nTotal Berat: " << totalWeight << endl;
    cout << "Total Profit: " << totalProfit << endl;
}

// Pendekatan Greedy
void greedyKnapsack(vector<Item> items, int capacity, int mode) {
    if (mode == 1) {
        cout << "\n--- Greedy 1: Berdasarkan Profit Terbesar ---\n";
        sort(items.begin(), items.end(), [](Item a, Item b) {
            return a.profit > b.profit;
        });
    } else if (mode == 2) {
        cout << "\n--- Greedy 2: Berdasarkan Berat Terkecil ---\n";
        sort(items.begin(), items.end(), [](Item a, Item b) {
            return a.weight < b.weight;
        });
    } else if (mode == 3) {
        cout << "\n--- Greedy 3: Berdasarkan Rasio Profit/Berat ---\n";
        sort(items.begin(), items.end(), [](Item a, Item b) {
            return a.ratio > b.ratio;
        });
    }

    printSelectedItems(items, capacity);
}

int main() {
    int weights[MAX_ITEMS];
    int profits[MAX_ITEMS];
    vector<Item> items;

    // Identitas
    cout << "==========================================\n";
    cout << "Nama  : SEPTIAN HANIF LUTHFI\n";
    cout << "NIM   : 23533730\n";
    cout << "Kelas : 4A INFORMATIKA\n";
    cout << "==========================================\n";

    // Input weight
    cout << "\nMasukkan bobot untuk masing-masing objek:\n";
    for (int i = 0; i < MAX_ITEMS; i++) {
        cout << "Bobot untuk Objek ke-" << i + 1 << ": ";
        cin >> weights[i];
    }

    // Input profit manual dari user
    cout << "\nMasukkan profit untuk masing-masing objek:\n";
    for (int i = 0; i < MAX_ITEMS; i++) {
        cout << "Profit untuk Objek ke-" << i + 1 << ": ";
        cin >> profits[i];
    }

    // Buat item
    for (int i = 0; i < MAX_ITEMS; i++) {
        Item itm;
        itm.index = i;
        itm.weight = weights[i];
        itm.profit = profits[i];
        itm.ratio = (double)profits[i] / weights[i];
        items.push_back(itm);
    }

    // Tampilkan data awal
    cout << "\nData Berat dan Profit:\n";
    cout << "Objek\tWeight\tProfit\tRatio\n";
    for (auto itm : items) {
        cout << itm.index + 1 << "\t"
             << itm.weight << "\t"
             << itm.profit << "\t"
             << fixed << setprecision(2) << itm.ratio << "\n";
    }

    // Jalankan 3 pendekatan greedy
    greedyKnapsack(items, CAPACITY, 1);
    greedyKnapsack(items, CAPACITY, 2);
    greedyKnapsack(items, CAPACITY, 3);

    return 0;
}