fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Structure for an item
  5. typedef struct {
  6.     int weight;
  7.     int value;
  8.     double ratio; // value/weight
  9. } Item;
  10.  
  11. // Comparator function for sorting items by ratio (descending order)
  12. int compare(const void *a, const void *b) {
  13.     double r1 = ((Item *)b)->ratio;
  14.     double r2 = ((Item *)a)->ratio;
  15.     return (r1 > r2) - (r1 < r2);
  16. }
  17.  
  18. // Function to solve the Fractional Knapsack Problem
  19. double fractionalKnapsack(int W, Item items[], int n) {
  20.     // Sorting items based on value/weight ratio
  21.     qsort(items, n, sizeof(Item), compare);
  22.  
  23.     double maxValue = 0.0; // Maximum value we can achieve
  24.     int currentWeight = 0; // Current weight in knapsack
  25.  
  26.     for (int i = 0; i < n; i++) {
  27.         // If the entire item can be picked
  28.         if (currentWeight + items[i].weight <= W) {
  29.             currentWeight += items[i].weight;
  30.             maxValue += items[i].value;
  31.         } 
  32.         // If only a fraction of the item can be picked
  33.         else {
  34.             int remainingWeight = W - currentWeight;
  35.             maxValue += items[i].ratio * remainingWeight;
  36.             break; // Knapsack is full
  37.         }
  38.     }
  39.  
  40.     return maxValue;
  41. }
  42.  
  43. // Driver code
  44. int main() {
  45.     int n, W;
  46.  
  47.     printf("Enter the number of items: ");
  48.     scanf("%d", &n);
  49.  
  50.     Item items[n];
  51.  
  52.     printf("Enter the weight and value of each item:\n");
  53.     for (int i = 0; i < n; i++) {
  54.         scanf("%d %d", &items[i].weight, &items[i].value);
  55.         items[i].ratio = (double)items[i].value / items[i].weight;
  56.     }
  57.  
  58.     printf("Enter the capacity of the knapsack: ");
  59.     scanf("%d", &W);
  60.  
  61.     double maxValue = fractionalKnapsack(W, items, n);
  62.     printf("Maximum value in the knapsack = %.2f\n", maxValue);
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
45
stdout
copy 
Enter the number of items: Enter the weight and value of each item:
Enter the capacity of the knapsack: Maximum value in the knapsack = 32814.12
https://ideone.com/Pj9SKp
language:
C++14 (gcc 8.3)
created:
11 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!