Fractional Knapsack

 Fractional Knapsack


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

typedef struct {
    double value;
    double weight;
} Item;

int compare(const void* a, const void* b) {
    Item* itemA = (Item*)a;
    Item* itemB = (Item*)b;
    double ratioA = itemA->value / itemA->weight;
    double ratioB = itemB->value / itemB->weight;
    if (ratioA > ratioB)
        return -1;
    else if (ratioA < ratioB)
        return 1;
    else
        return 0;
}

double fractionalKnapsack(int capacity, Item items[], int n) {
    qsort(items, n, sizeof(Item), compare);

    double totalValue = 0.0;
    int i;

    for (i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            totalValue += items[i].value;
            capacity -= items[i].weight;
        } else {
            totalValue += (capacity / items[i].weight) * items[i].value;
            break;
        }
    }

    return totalValue;
}

int main() {
    int capacity = 50;
    Item items[] = {
        { 60, 10 },
        { 100, 20 },
        { 120, 30 }
    };
    int n = sizeof(items) / sizeof(items[0]);

    double maxValue = fractionalKnapsack(capacity, items, n);

    printf("Maximum value: %.2f\n", maxValue);

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

1.Import and Export(How to read csv file using manualvfunction)

#!/usr/bin/env python # coding: utf-8 # In[5]: # Week1: Write a python program to import and export data from/to CSV file ######################################################################### ## (1) How to Read CSV File using Manual Function import pandas as pd def load_csv ( filepath ):     data = []     col = []     checkcol = False     with open (filepath) as f:         for val in f.readlines():             val = val.strip()             val = val.split( ',' )             if checkcol is False :                 col = val                 checkcol = True             else :                 data.append(val)     df = pd.DataFrame( data = data, columns = col)   ...
Read more

K Means_Clustering

  #!/usr/bin/env python # coding: utf-8 # In[3]: import pandas as pd import numpy as np import matplotlib.pyplot as plt df = pd.read_csv( r "C: \U sers \91 887 \O neDrive\Desktop \M achine_Learning\week4_Mall_Customers.csv" ) x = df.iloc[:, [ 3 , 4 ]].values # In[4]: from sklearn.cluster import KMeans wcss_list = [] for i in range ( 1 , 11 ):     kmeans = KMeans( n_clusters = i, init = 'k-means++' , random_state = 42 )     kmeans.fit(x)     wcss_list.append(kmeans.inertia_) plt.plot( range ( 1 , 11 ), wcss_list) plt.title( 'The Elobw Method Graph' ) plt.xlabel( 'Number of clusters(k)' ) plt.ylabel( 'wcss_list' ) plt.show() # In[ ]:
Read more

How to became a junior Engineer

How to become a junior Engineer. We know that about a junior Engineer. We and all have only a question  How I Became? I want to explain you. Every Central and state Government has Organized exam for preparing junior Engineeringlike (polytechnic , Diploma cources etc) Step 1 . Junior Engineer course exam  is organized every year on the month of April,may,and June. Fill the registration appearing form . Step 2. prepare the examination for the junior engineering. Step 3. Appear the examination on the junior engineering Step 4.   If you will pass out the exam then you will appear on the counselling .this time counselling is organized on online so you will fill your choice  branch like(civile engineering,electrical engineering, mechanical engineering, computer science and engineering, mining engineering etc)and choice your college . Step 4.  After fill your choice and college you will allotted a particular branch and college if you like the branch and colle...
Read more