CSE2012 PP1 Q4 TRY 1

/*
.  There are n items in the suitcase of a traveler. On boarding the flight, the airline company told him that his suitcase is over weight than the allowed capacity W and asked him deload some items and not to carry more than W. He knows weight of each item. Devise an algorithm to find out which items to be discarded so that he can carry max. weight W. (assume the weight of the suitcase is ignored).
*/

#include <stdio.h>
#include <stdlib.h>


void printArr(float arr[], int size){
    int i;
    for(i = 0; i < size; i++){
        printf("%f ", arr[i]);
    }
    printf("\n");
}


void merge(float arr[], int l, int m, int n){
    int i, j, k;
    int n1 = m-l+1;
    int n2 = n-m;
    float *left, *right;
    left = (float*)malloc(sizeof(float)*n1);
    right = (float*)malloc(sizeof(float)*n2);


    for(i = 0; i < n1; i++){
        left[i] = arr[i+l];
    }
    for(j = 0; j < n2; j++){
        right[j] = arr[m+1+j];
    }

    i=0; j=0; k=l;

    while(i<n1 && j<n2){
        if (left[i] <= right[j]){
            arr[k++] = left[i++];
        }
        else{
            arr[k++] = right[j++];
        }
    }

    while(i < n1){
        arr[k++] = left[i++];
    }
    while(j < n2){
        arr[k++] = right[j++];
    }
}

void mergeSort(float arr[], int l, int r){
    if (l>=r){
        return;
    }
    int m = l + (r-l)/2; // m = (l+r)/2
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
}

void solve(){
    unsigned int size;
    float *arr;
    float w;
    //input
    printf("\nEnter the weight limit: ");
    scanf("%f", &w);

    printf("\nEnter the number of items: ");
    scanf("%u", &size);
    arr = (float*)malloc(sizeof(float)*size);

    printf("\nEnter the weights: ");
    int i;
    for(i = 0; i < size; i++){
        scanf("%f", &arr[i]);
    }

    // solving naive
    //printf("\n");
    //printArr(arr, size);
    mergeSort(arr, 0, size);
    //printArr(arr, size);
    int currWeight = 0;
    for(i = 0; i < size; i++){
        if (currWeight + arr[i] > w){
            break;
        }
        currWeight += arr[i];
    }
    //
    //printf("\n%d items of weights ", i+1);
    //int j;
    //for(j = 0; j <= i; j++){
    //    printf("%d ", arr[j]);
    //}
    //printf("can be allowed to carry");
    //

    printf("\n%d items of weights: ", size-i);
    for(i; i<size;i++){
        printf("%f ", arr[i]);
    }
    printf("\nNeed to be discarded\n");
}

int main(){
    solve();
    return 0;
}