-1

What am I missing in this code? I want to print selected items with 0 or 1, but I am not getting proper output in this fractional-knapsack test case.

fractional-knapsack
First line contains number of total items n Next n lines contain values and weights of ith item, where 1<=i<=n Last line contains the capacity or total weight (W) of knapsack Constraints

Number of total items: 1< n <=10
Capacity of knapsack or Weight W: 10 <= W <=100
Output Format

First line contain total value or profit of knapsack second line contain array of n size with value 0 or 1

#include <bits/stdc++.h>
using namespace std;

struct Item
{
    double weight;
    double value;
    int selected=0;
    double wByv; // Weight-to-value ratio
};

bool compareItems(const Item &a, const Item &b)
{
    return a.wByv > b.wByv;
}

void fractionalKnapsack(int n, double knapsackWeight, Item items[])
{
    sort(items, items + n, compareItems);

    double totalValue = 0.0;
    double currentWeight = 0.0;

    int selectedItem[n] = {0}; // Initialize with all zeros

    for (int i = 0; i < n; i++)
    {
        if (currentWeight + items[i].weight <= knapsackWeight)
        {
            // Take the whole item
            totalValue += items[i].value;
            currentWeight += items[i].weight;
            items[i].selected = 1; // Mark the item as selected
        }
        else
        {
            // Take a fraction of the item to fill the knapsack to capacity
            double remainingCapacity = knapsackWeight - currentWeight; // Calculate the remaining capacity in the knapsack
            double fraction = remainingCapacity / items[i].weight;     // Calculate the fraction of the item that fits
            double itemValueInKnapsack = fraction * items[i].value;    // Calculate the value of the fraction that fits
            totalValue += itemValueInKnapsack;
            items[i].selected = 1; // Mark the item as selected
             // Mark the item as selected
            break;
        }
    }

    cout << totalValue << endl;
    for (int i = 0; i < n; i++)
    {
        cout << items[i].selected << " ";
    }
}

int main()
{
    int n;
    cin >> n;
    Item items[n];
    for (int i = 0; i < n; i++)
    {
        cin >> items[i].value >> items[i].weight;
        items[i].wByv = items[i].value / items[i].weight; // Calculate weight-to-value ratio
    }

    double knapsackWeight;
    cin >> knapsackWeight;

    fractionalKnapsack(n, knapsackWeight, items);

    return 0;
}

incorrect for me

Input (stdin)

5
30  5
40  10
45  15
77  22
90  25
60
Your Output (stdout)

230
1 1 1 1 0 
Expected Output

230
1 1   0   1   1
Compiler Message

Wrong Answer

corrected

Input (stdin)

4
100   10
280   40
120   20
120   24
60
Your Output (stdout)

440
1 1 1 0 
Expected Output

440
1 1   1   0

4
10  5
20  10
30  15
40  20
40
Your Output (stdout)

80
1 1 1 1 
Expected Output

80
1 1   1   1


output should be like 
5
30  5
40  10
45  15
77  22
90  25
60
Your Output (stdout)

230
1 1 1 1 0 
Expected Output

230
1 1   0   1   1
Compiler Message

Wrong Answer
JaMiT
  • 14,422
  • 4
  • 15
  • 31
  • 1
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – 463035818_is_not_an_ai Sep 01 '23 at 07:12
  • [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Jesper Juhl Sep 01 '23 at 10:47
  • [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Jesper Juhl Sep 01 '23 at 10:48
  • [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – Jesper Juhl Sep 01 '23 at 10:49
  • Most of the text in your question is quoting the problem you were given. This is often a sign that the asker has not put in enough effort to isolate the question. Could you add two to three paragraphs describing the debugging you've done so far? Details like which variable holds a wrong value would be helpful to focus the question. *They would also help you construct a better [mre]. Perhaps you can simplify your example to the point where quoting the problem is no longer relavant?* – JaMiT Sep 01 '23 at 21:55

0 Answers0