Contoh program algoritma greedy bahasa c (knapsack problem)

contoh program algoritma greedy bahasa c (knapsack problem)

kasus : barang yang akan diangkut pada mobil pengangkut barang

#include <stdio.h>
#include <string.h>

int jumlah = 0;
int kapasitas;

int beratMasuk[20];
char namaMasuk[20][20];
int jumlahMasuk = 0;
void freightCar(char nama[20], int berat, int index){
    kapasitas = kapasitas - berat;
    strcpy(namaMasuk[index],nama);
    beratMasuk[index] = berat;
    jumlahMasuk = jumlahMasuk + 1;
}

int main(){
    printf("kasus : barang yang akan dimasukkan ke mobil pengangkut barang\n");
    printf("Masukkan jumlah Barang (max 20 hehe): ");scanf("%d",&jumlah);
    if(jumlah > 20){
        printf("max 20 yak\n");
        main();
    }
    printf("Masukkan kapasitas penampung : ");scanf("%d",&kapasitas);
    int berat[jumlah];
    char nama[jumlah][20];
    for(int i = 0; i < jumlah;  i++){
        printf("Nama Barang : ");scanf("%s",&nama[i]);
        printf("Berat : ");scanf("%d",&berat[i]);
    }
  
    //shorting
    for (int i = 0; i < jumlah; i++) {
      for (int j = i + 1; j < jumlah; j++) {
         if (berat[i] < berat[j]) {
             int temp = berat[j];
             berat[j] = berat[i];
            berat[i] = temp;
          
            char temp1[20];
            strcpy(temp1,nama[j]);
            strcpy(nama[j],nama[i]);
            strcpy(nama[i],temp1);
         }
      }
   }
 
   //masukkan barang
   int i = 0;
   while(i < jumlah && kapasitas >= berat[i]){
        freightCar(nama[i],berat[i],i);
        i = i+1;
   }
  
    //printout
    printf("==Barang Masuk==\n");
    for(int i = 0; i < jumlahMasuk; i++){
        printf("Nama Barang : %s \n",namaMasuk[i]);
        printf("Berat : %d \n",beratMasuk[i]);
        printf("----------------\n");
    }
    printf("================\n");
    printf("Sisa Kapasitas : %d",kapasitas);
}