Tuesday, November 12, 2019

C Program For Greedy Algorithm (knapsack problem)

C Program for greedy algorithm
case : knapsack



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

int amount = 0;
int capacity;

int weightIn[20];
char nameIn[20][20];
int amountIn = 0;
void freightCar(char name[20], int weight, int index){
            capacity = capacity - weight;
            strcpy(nameIn[index],name);
            weightIn[index] = weight;
            amountIn = amountIn + 1;
}

int main(){
            printf("input amount of items (max 20): ");scanf("%d",&amount);
            if(amount > 20){
                        printf("max 20 \n");
                        main();
            }
            printf("input capacity : ");scanf("%d",&capacity);
            int weight[amount];
            char name[amount][20];
            for(int i = 0; i < amount;  i++){
                        printf("name : ");scanf("%s",&name[i]);
                        printf("weight : ");scanf("%d",&weight[i]);
            }
         
            //shorting
            for (int i = 0; i < amount; i++) {
                        for (int j = i + 1; j < amount; j++) {
                                     if (weight[i] < weight[j]) {
                                                int temp = weight[j];
                                                weight[j] = weight[i];
                                                weight[i] = temp;
                                                char temp1[20];
                                                strcpy(temp1,name[j]);
                                                strcpy(name[j],name[i]);
                                                strcpy(name[i],temp1);
                                    }
                        }
            }

            //input
            int i = 0;
            while(i < amount && capacity >= weight[i]){
                        freightCar(name[i],weight[i],i);
                        i = i+1;
           }
         
            //printout
            printf("==List Items==\n");
            for(int i = 0; i < amountIn; i++){
                        printf("name : %s \n",nameIn[i]);
                        printf("weight : %d \n",weightIn[i]);
                        printf("----------------\n");
            }
            printf("================\n");
            printf("Remaining capacity : %d",capacity);
}

Share:

0 comments:

Post a Comment

Powered by Blogger.

Labels

Pages

Pages

Featured Post

Penulisan Kata dalam Ejaan Bahasa Indonesia

Penulisan Kata dalam Ejaan Bahasa Indonesia Kata Dasar Kata dasar ditulis sebagai satu kesatuan. Contoh: Kantor pajak penuh sesak. Kat...