fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. int main() {
  6.     // baca seluruh input dari stdin ke buffer
  7.     char buf[2000];
  8.     size_t pos = 0;
  9.     buf[0] = '\0';
  10.     while (fgets(buf + pos, sizeof(buf) - pos, stdin)) {
  11.         pos = strlen(buf);
  12.         if (pos >= sizeof(buf)-1) break;
  13.         // jika sudah membaca satu baris penuh, tetap kumpulkan seluruh input (toleran)
  14.     }
  15.  
  16.     // ganti koma dengan spasi untuk memudahkan parsing
  17.     for (size_t i = 0; i < strlen(buf); ++i) {
  18.         if (buf[i] == ',') buf[i] = ' ';
  19.     }
  20.  
  21.     // tokenisasi dan konversi semua integer yang ada
  22.     int nums[1000];
  23.     int cnt = 0;
  24.     char *tok = strtok(buf, " \t\r\n");
  25.     while (tok) {
  26.         char *endptr;
  27.         long val = strtol(tok, &endptr, 10);
  28.         if (endptr != tok) {
  29.             nums[cnt++] = (int)val;
  30.         }
  31.         tok = strtok(NULL, " \t\r\n");
  32.     }
  33.  
  34.     if (cnt < 1) return 0;
  35.  
  36.     int idx = 0;
  37.     int n = nums[idx++];                     // jumlah item
  38.     if (cnt < 1 + 2*n + 1) {
  39.         // input tidak lengkap
  40.         return 0;
  41.     }
  42.  
  43.     int *w = (int*)malloc(sizeof(int) * n);
  44.     int *v = (int*)malloc(sizeof(int) * n);
  45.     if (!w || !v) return 0;
  46.  
  47.     for (int i = 0; i < n; ++i) w[i] = nums[idx++];
  48.     for (int i = 0; i < n; ++i) v[i] = nums[idx++];
  49.     int cap = nums[idx++];
  50.  
  51.     if (cap < 0) cap = 0;
  52.  
  53.     // DP 0-1 knapsack (memaksimalkan nilai)
  54.     // gunakan array 1D untuk efisiensi: dp[j] = maksimum nilai untuk kapasitas j
  55.     int *dp = (int*)calloc(cap + 1, sizeof(int));
  56.     if (!dp) {
  57.         free(w); free(v);
  58.         return 0;
  59.     }
  60.  
  61.     for (int i = 0; i < n; ++i) {
  62.         int wi = w[i];
  63.         int vi = v[i];
  64.         // iterasi mundur agar 0-1 knapsack benar
  65.         for (int j = cap; j >= wi; --j) {
  66.             int cand = dp[j - wi] + vi;
  67.             if (cand > dp[j]) dp[j] = cand;
  68.         }
  69.     }
  70.  
  71.     // hasil optimal = dp[cap]
  72.     printf("%d", dp[cap]);
  73.  
  74.     free(w); free(v); free(dp);
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
8
3 10 6 7 9 10 7 5
1 10 8 1 7 8 9 18
35
stdout
copy 
46
https://ideone.com/w5Oy7p
language:
C (gcc 8.3)
created:
8 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!