Skip to main content

Code & Examples 2

Knapsack Problem

#include <bits/stdc++.h>
using namespace std;

// Function untuk mencari profit maksimal dalam suatu knapsack
int knapsack(int W, vector<int> &val, vector<int> &wt) {

    // Inisialisasi array dp dengan nilai awal 0
    vector<int> dp(W + 1, 0);

    // Mengambil setiap item, mulai dari item ke-1 hingga item ke-n
    for (int i = 1; i <= wt.size(); i++) {
        
        // Mulai dari belakang, sehingga kita juga memiliki data dari
        // perhitungan sebelumnya dari i-1 item dan menghindari duplikasi
        for (int j = W; j >= wt[i - 1]; j--) {
            dp[j] = max(dp[j], dp[j - wt[i - 1]] + val[i - 1]);
        }
    }
    return dp[W];
}

int main() {
    vector<int> val = {1, 2, 3};
    vector<int> wt = {4, 5, 1};
    int W = 4;

    cout << knapsack(W, val, wt) << endl;
    return 0;
}

Penjelasan Program:
Kode di atas sudah bersifat optimized karena menghemat penggunaan memori dan waktu eksekusi. Analogi untuk program ini adalah sebagai berikut:

  • Kita memiliki sebuah tas (knapsack) dengan kapasitas tertentu (W).
  • Kita memiliki beberapa barang (items) dengan nilai (val) dan berat (wt) tertentu.
  • Tujuan kita adalah mengisi tas tersebut dengan barang-barang sehingga nilai total barang di dalam tas maksimal tanpa melebihi kapasitas tas.
  • Kita menggunakan pendekatan dinamis (dynamic programming) untuk menyelesaikan masalah ini dengan efisien.
  • Pertama-tama, kita iterasi setiap barang, dan untuk setiap barang, kita iterasi kapasitas tas dari belakang ke depan (misal dari berat maksimum ke 0).
  • Dengan cara ini, nanti kita akan cari maksimal nilai yang bisa dimasukkan ke dalam tas tanpa melebihi kapasitasnya.
  • Kode tersebut sudah mencakup situasi membandingkan antara menggunakan nilai barang dengan weight tertinggi atau menambahkan nilai barang dengan weight lebih rendah dengan kapasitas tas yang lebih kecil.
Back to top