fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main() {
  7.     int n; 
  8.     cin >> n; // jumlah barang
  9.  
  10.     vector<int> berat(n);
  11.     vector<int> nilai(n);
  12.  
  13.     // Input berat barang
  14.     for (int i = 0; i < n; i++) {
  15.         cin >> berat[i];
  16.     }
  17.  
  18.     // Input nilai barang
  19.     for (int i = 0; i < n; i++) {
  20.         cin >> nilai[i];
  21.     }
  22.  
  23.     int kapasitas;
  24.     cin >> kapasitas; // kapasitas maksimum
  25.  
  26.     // Buat tabel DP
  27.     vector<vector<int>> dp(n + 1, vector<int>(kapasitas + 1, 0));
  28.  
  29.     // Proses perhitungan DP
  30.     for (int i = 1; i <= n; i++) {
  31.         for (int w = 1; w <= kapasitas; w++) {
  32.             if (berat[i - 1] <= w) {
  33.                 dp[i][w] = max(nilai[i - 1] + dp[i - 1][w - berat[i - 1]], dp[i - 1][w]);
  34.             } else {
  35.                 dp[i][w] = dp[i - 1][w];
  36.             }
  37.         }
  38.     }
  39.  
  40.     cout << dp[n][kapasitas] << endl;
  41.     return 0;
  42. }
  43.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5
5 4 7 8 10
10 5 7 12 8
20
stdout
copy 
29
https://ideone.com/PxO6yQ
language:
C++ (gcc 8.3)
created:
4 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!