fork download
copy 
  1. #include <stdio.h>
  2.  
  3. int main() {
  4.     int n;                    // jumlah item
  5.     int w[100], v[100];       // berat dan nilai
  6.     int cap;                  // kapasitas maksimum
  7.     char c;                   // untuk baca koma
  8.     int i, j;
  9.  
  10.     // baca input sesuai format
  11.     scanf("%d", &n);
  12.     scanf("%c", &c); // baca koma pertama
  13.  
  14.     for (i = 0; i < n; i++) scanf("%d", &w[i]);
  15.     scanf("%c", &c); // baca koma kedua
  16.     for (i = 0; i < n; i++) scanf("%d", &v[i]);
  17.     scanf("%c", &c); // baca koma ketiga
  18.     scanf("%d", &cap);
  19.  
  20.     // dynamic programming knapsack
  21.     int dp[101][101] = {0};
  22.     for (i = 1; i <= n; i++) {
  23.         for (j = 0; j <= cap; j++) {
  24.             if (w[i - 1] <= j) {
  25.                 int pilih = v[i - 1] + dp[i - 1][j - w[i - 1]];
  26.                 if (pilih > dp[i - 1][j])
  27.                     dp[i][j] = pilih;
  28.                 else
  29.                     dp[i][j] = dp[i - 1][j];
  30.             } else {
  31.                 dp[i][j] = dp[i - 1][j];
  32.             }
  33.         }
  34.     }
  35.  
  36.     // cari kombinasi yang diambil
  37.     int total_berat = 0;
  38.     int total_item = 0;
  39.     int sisa = cap;
  40.     for (i = n; i > 0; i--) {
  41.         if (dp[i][sisa] != dp[i - 1][sisa]) {
  42.             total_item++;
  43.             total_berat += w[i - 1];
  44.             sisa -= w[i - 1];
  45.         }
  46.     }
  47.  
  48.     // tampilkan tanpa spasi
  49.     printf("%d%d", total_item, total_berat);
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
5
5 4 7 8 10
10 5 7 12 8
20
stdout
copy 
320
https://ideone.com/srEtnD
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!