Scribd
Upload
42 views4 pages

Greedy Knapsack Problem in C

The document presents a C program that implements a greedy solution to the Fractional Knapsack problem. It defines a structure for items, sorts them based on their value-to-weight ratio, and calculates the maximum value that can be carried in the knapsack. The program outputs the items taken and their respective weights and values, along with the total maximum value.

Uploaded by

myjio0536
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
42 views4 pages

Greedy Knapsack Problem in C

The document presents a C program that implements a greedy solution to the Fractional Knapsack problem. It defines a structure for items, sorts them based on their value-to-weight ratio, and calculates the maximum value that can be carried in the knapsack. The program outputs the items taken and their respective weights and values, along with the total maximum value.

Uploaded by

myjio0536
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

C Program: Knapsack Problem using Greedy Solution

#include <stdio.h>

// Structure to represent an item with weight, value, and value/weight ratio

struct Item {

int weight;

int value;

float ratio; // value-to-weight ratio

};

// Function to swap two items (used in sorting)

void swap(struct Item *a, struct Item *b) {

struct Item temp = *a;

*a = *b;

*b = temp;

// Function to sort items by value/weight ratio in descending order

void sortItems(struct Item items[], int n) {

for (int i = 0; i < n - 1; i++) {

for (int j = i + 1; j < n; j++) {

if (items[i].ratio < items[j].ratio) {

swap(&items[i], &items[j]);

// Function to solve Fractional Knapsack problem

void knapsack(struct Item items[], int n, int capacity) {

int curWeight = 0; // Current weight in knapsack

float finalValue = 0.0; // Result (max value)


C Program: Knapsack Problem using Greedy Solution

printf("\nItems taken into knapsack:\n");

// Loop through all items

for (int i = 0; i < n; i++) {

// If adding this item does not exceed capacity

if (curWeight + items[i].weight <= capacity) {

curWeight += items[i].weight;

finalValue += items[i].value;

printf("Item %d -> weight: %d, value: %d (100%% taken)\n", i + 1, items[i].weight,


items[i].value);

// If item cannot be fully added, take fraction

else {

int remain = capacity - curWeight;

finalValue += items[i].value * ((float)remain / items[i].weight);

printf("Item %d -> weight: %d, value: %d (%.2f%% taken)\n", i + 1, items[i].weight,


items[i].value, (remain * 100.0 / items[i].weight));

break; // knapsack is full

printf("\nMaximum value in Knapsack = %.2f\n", finalValue);

// Driver code

int main() {

int n = 3; // Number of items

int capacity = 50; // Capacity of knapsack

// Define items (weight, value)

struct Item items[3] = {


C Program: Knapsack Problem using Greedy Solution
{10, 60, 0},

{20, 100, 0},

{30, 120, 0}

};

// Compute value-to-weight ratio

for (int i = 0; i < n; i++) {

items[i].ratio = (float)items[i].value / items[i].weight;

// Sort items by ratio

sortItems(items, n);

printf("Knapsack capacity = %d\n", capacity);

printf("Items (after sorting by value/weight ratio):\n");

for (int i = 0; i < n; i++) {

printf("Item %d -> weight: %d, value: %d, ratio: %.2f\n", i + 1, items[i].weight, items[i].value,
items[i].ratio);

// Solve knapsack

knapsack(items, n, capacity);

return 0;

}
C Program: Knapsack Problem using Greedy Solution
Explanation of Code

1. Each item has weight, value, and ratio (value/weight).


2. Items are sorted in descending order of ratio (greedy choice).
3. Keep adding items until knapsack is full:
a. If full item fits → take whole item.
b. Else → take fractional part of it.
4. Calculate maximum value.

Sample Output

For items {(10,60), (20,100), (30,120)} and capacity 50:

Knapsack capacity = 50

Items (after sorting by value/weight ratio):

Item 1 -> weight: 10, value: 60, ratio: 6.00

Item 2 -> weight: 20, value: 100, ratio: 5.00

Item 3 -> weight: 30, value: 120, ratio: 4.00

Items taken into knapsack:

Item 1 -> weight: 10, value: 60 (100% taken)

Item 2 -> weight: 20, value: 100 (100% taken)

Item 3 -> weight: 30, value: 120 (66.67% taken)

Maximum value in Knapsack = 240.00

Common questions

Powered by AI

The greedy algorithm efficiently solves the fractional knapsack problem by prioritizing items based on their value-to-weight ratio. The key steps involved include: (1) calculating the value-to-weight ratios for each item, (2) sorting the items in descending order based on these ratios, (3) iteratively adding items to the knapsack in this order until the knapsack is full, and (4) if an item cannot be fully added due to capacity constraints, adding a fractional part of the item to maximize the total value. This approach ensures that the maximum possible value is obtained with the given capacity .

When the greedy algorithm encounters an item that cannot be fully added to the knapsack due to capacity limits, it calculates the percentage to include by dividing the remaining capacity by the item's weight. This fraction (expressed as a percentage) is then applied to the item's value to determine the fractional item value to add to the knapsack, thereby maximizing the total value within the constraints without exceeding the knapsack's capacity .

The value-to-weight ratio is calculated by dividing an item's value by its weight. This ratio is significant because it indicates the item's contribution to the knapsack's total value per unit weight. In the greedy solution, prioritizing items with the highest value-to-weight ratio ensures that the knapsack reaches the maximum possible value for the given capacity, as high-ratio items are added first .

Fractional items in the greedy solution are used when an item cannot be fully added to the knapsack due to capacity constraints. Instead of excluding the item altogether, the algorithm adds a fraction of the item proportional to the remaining capacity. This is handled by calculating the fraction as (remaining capacity) / (item weight), and adding to the final value the item's total value multiplied by this fraction. This ensures that the knapsack's value is maximized while fully utilizing available capacity .

The greedy algorithm is considered optimal for the fractional knapsack problem because it allows items to be divided and taken in proportions, enabling a maximum value to be reached with each selection. The algorithm makes locally optimal choices by selecting items with the highest value-to-weight ratio, which leads to a global maximum. In contrast, for the 0/1 version, where items cannot be divided, the greedy algorithm may fail to find the optimum as the problem's nature requires considering all item combinations to maximize the total value .

Sorting items by value-to-weight ratio is crucial because it ensures that items with the highest ratio, which contribute the most value per unit weight, are considered first. This approach maximizes the total value in the knapsack for a given capacity by allowing the inclusion of highly valuable items upfront. This step aligns with the greedy method's strategy of making locally optimal choices that lead to a globally optimal solution .

The greedy algorithm is computationally efficient for solving the fractional knapsack problem as it primarily involves sorting and a linear pass through the sorted items. Sorting takes O(n log n) time, and the subsequent selection process operates in O(n), where n is the number of items. This efficiency makes the greedy approach suitable for large input sizes, as the sorting dominates the complexity. However, it hinges on efficient sorting, and while optimal for the fractional version, it limits applicability to problems without such divisibility concessions .

When ties occur in value-to-weight ratios, the greedy algorithm requires a secondary criterion to decide the order of item inclusion. Common strategies include prioritizing items with lower weight or higher absolute value if the ratios are equal. This decision can influence the final composition of the knapsack when capacity restrictions play a role in marginal differences, thus impacting the resultant maximum value. Efficient tie-breaking is crucial for maintaining the optimality of the greedy approach, especially when that factor significantly affects outcome variations .

The greedy approach is not optimal for the 0/1 knapsack problem because it does not account for the problem's indivisibility constraints; items cannot be taken fractionally. The greedy method might choose items that maximize immediate value based on the ratio, potentially leading to suboptimal total value due to remaining unutilized capacity. Unlike the fractional version, the 0/1 knapsack requires exploring combinations of items thoroughly, which may not be efficiently addressed by greedy heuristics .

The choice of sorting items by value-to-weight ratio directly affects the greedy algorithm's outcome by ensuring that the highest value items per weight unit are prioritized. This sorting aligns with the goal of maximizing total knapsack value, as adding items in this order optimally utilizes available capacity, leading to an optimal global result in the fractional version. Incorrect sorting or neglect of this step could result in suboptimal choices and reduced total knapsack value, demonstrating the critical nature of sorting in guiding the algorithm's decision-making .

You might also like