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 ConstraintsNumber of total items: 1< n <=10
Capacity of knapsack or Weight W: 10 <= W <=100
Output FormatFirst 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