fork download 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // Fungsi untuk menghitung solusi knapsack 0/1
  6. int knapsack(int kapasitas, vector<int> berat, vector<int> nilai, int n) {
  7.     vector<vector<int>> dp(n + 1, vector<int>(kapasitas + 1, 0));
  8.  
  9.     for (int i = 1; i <= n; i++) {
  10.         for (int w = 1; w <= kapasitas; w++) {
  11.             if (berat[i - 1] <= w)
  12.                 dp[i][w] = max(nilai[i - 1] + dp[i - 1][w - berat[i - 1]], dp[i - 1][w]);
  13.             else
  14.                 dp[i][w] = dp[i - 1][w];
  15.         }
  16.     }
  17.     return dp[n][kapasitas];
  18. }
  19.  
  20. int main() {
  21.     int n = 5; // jumlah barang
  22.     vector<int> berat = {5, 4, 7, 8, 10};
  23.     vector<int> nilai = {10, 5, 7, 12, 8};
  24.     int kapasitas = 20;
  25.  
  26.     cout << "Implementasi dan Pengujian Solusi Knapsack 0/1\n";
  27.     cout << "Jumlah barang: " << n << endl;
  28.     cout << "Kapasitas maksimum: " << kapasitas << endl;
  29.  
  30.     int hasil = knapsack(kapasitas, berat, nilai, n);
  31.  
  32.     cout << "Nilai maksimum yang dapat diperoleh: " << hasil << endl;
  33.  
  34.     // Uji hasil sesuai contoh
  35.     if (hasil == 29)
  36.         cout << "✅ Hasil benar (29)" << endl;
  37.     else
  38.         cout << "❌ Hasil salah, seharusnya 29" << endl;
  39.  
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin 
8
3 10 6 7 9 10 7 5
1 10 8 1 7 8 9 18
35
stdout 
Implementasi dan Pengujian Solusi Knapsack 0/1
Jumlah barang: 5
Kapasitas maksimum: 20
Nilai maksimum yang dapat diperoleh: 29
✅ Hasil benar (29)
https://ideone.com/bHOpVf
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!