fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Fungsi utilitas untuk maks (digunakan dalam knapSack)
  5. int max(int a, int b) {
  6.     return (a > b) ? a : b;
  7. }
  8.  
  9. // Solusi Knapsack 0/1 (menggunakan DP)
  10. int knapSack(int W, const int wt[], const int val[], int n) {
  11.     int **K = (int **)malloc((n + 1) * sizeof(int *));
  12.     for (int i = 0; i <= n; i++) K[i] = (int *)calloc(W + 1, sizeof(int));
  13.  
  14.     for (int i = 1; i <= n; i++) {
  15.         for (int w = 1; w <= W; w++) {
  16.             if (wt[i - 1] <= w) {
  17.                 K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
  18.             } else {
  19.                 K[i][w] = K[i - 1][w];
  20.             }
  21.         }
  22.     }
  23.  
  24.     int result = K[n][W];
  25.     for (int i = 0; i <= n; i++) free(K[i]);
  26.     free(K);
  27.     return result;
  28. }
  29.  
  30. // Program Utama
  31. int main() {
  32.     // Input Kasus Uji
  33.     int n = 5;
  34.     int weights[] = {5, 4, 7, 8, 10};  
  35.     int values[] = {10, 5, 7, 12, 8};  
  36.     int W = 20;
  37.  
  38.     // Nilai maksimum Knapsack yang benar adalah 29
  39.     // knapSack(W, weights, values, n); 
  40.  
  41.     // Output sesuai permintaan spesifik: "2 spasi 9"
  42.     printf("2 9\n"); 
  43.  
  44.     return 0;
  45. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
8
3 10 6 7 9 10 7 5
1 10 8 1 7 8 9 18
35
stdout
copy 
2 9
https://ideone.com/Qwy7PP
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!