fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // Fungsi untuk menyelesaikan masalah knapsack 0/1
  8. int knapsack(int kapasitas, const vector<int>& berat, const vector<int>& nilai) {
  9.     int n = berat.size();
  10.     vector<vector<int>> dp(n + 1, vector<int>(kapasitas + 1, 0));
  11.  
  12.     for (int i = 1; i <= n; ++i) {
  13.         for (int w = 1; w <= kapasitas; ++w) {
  14.             if (berat[i - 1] <= w) {
  15.                 dp[i][w] = max(nilai[i - 1] + dp[i - 1][w - berat[i - 1]], dp[i - 1][w]);
  16.             } else {
  17.                 dp[i][w] = dp[i - 1][w];
  18.             }
  19.         }
  20.     }
  21.     return dp[n][kapasitas];
  22. }
  23.  
  24. int main() {
  25.     // Data uji
  26.     vector<int> nilai = {60, 100, 120};
  27.     vector<int> berat = {10, 20, 30};
  28.     int kapasitas = 50;
  29.  
  30.     // Menjalankan dan menampilkan hasil
  31.     int nilaiMaks = knapsack(kapasitas, berat, nilai);
  32.     cout << "Nilai maksimum dalam knapsack adalah: " << nilaiMaks << endl;
  33.  
  34.     return 0;
  35. }
  36.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
5 4 7 8 10
10 5 7 12 8
20
stdout
copy 
Nilai maksimum dalam knapsack adalah: 220
https://ideone.com/V2RS30
language:
C++ (gcc 8.3)
created:
3 hours 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!