6
\$\begingroup\$

A thief finds much more loot than his bag can fit. We have to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag.

For example has a bag which can fit at most 50 Kg of items. He has 3 items to choose from: the first item has a total value of $60 for 20 Kg, the second item has a total value of $100 for 50 Kg and the last item has a total value of $120 for 30 Kg.

So, if the thief takes the most of the item that costs more per unit Kg, he/she can make a better profit out of his/her thievery. In that case, he/she would take 30 Kgs of the third item, and 20 Kgs of the first item, resulting in a total of 50 Kgs (full capacity) with the total value of $180.

// THIS IS AN EXAMPLE OF THE FRACTIONAL KNAPSACK PROBLEM

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
double get_max_index(vector<int>, vector<int>);
double get_max_value(vector<int>, vector<int>, int);

int main() {

    int num_items, bag_capacity;
    cout << "Enter the number of items: " << endl;
    cin >> num_items;
    cout << "Enter the total capacity that the bag can support: " << endl;
    cin >> bag_capacity;

    vector<int> values;
    vector<int> weights;

    for (int i = 0; i < num_items; i++)
    {
        int buff_val = 0, buff_wgt = 0;
        cout << "Enter the value and weight of Item " << i + 1 << ": " << endl;
        cin >> buff_val >> buff_wgt;
        values.push_back(buff_val);
        weights.push_back(buff_wgt);
    }

    cout.precision(10);
    cout << "The maximum loot value that can be acquired is " << fixed << get_max_value(values, weights, bag_capacity) << "." << endl;          // Always display 'precision' number of digits

    return 0;
}

double get_max_index(vector<int> vals, vector<int> wgts){
    int max_index = 0;
    double max_val_per_wgt = 0;
    for (int i = 0; i < wgts.size(); i++)
    {
        if (wgts[i] != 0 && (double) vals[i] / wgts[i] > max_val_per_wgt)
        {
            max_val_per_wgt = (double) vals[i] / wgts[i];
            max_index = i;
        }
    }
    return max_index;
}

double get_max_value(vector<int> vals, vector<int> wgts, int capacity){

    double max_val = 0.0;
    for(int i = 0; i < wgts.size(); i++) {
        if (capacity == 0)
        {
            return max_val;             // There's no space left in the bag to carry
        }
        int max_value_index = get_max_index(vals, wgts);     // See which item has the best value per weight index
        double taken = capacity > wgts[max_value_index] ? wgts[max_value_index] : capacity;     // get the minimum of the item's weight and capacity left in the bag
        max_val += taken * (double) vals[max_value_index] / wgts[max_value_index];      // calculate value for the item's weight taken
        capacity -= taken;          // reduce capacity of the bag by the amount of weight of item taken
        wgts[max_value_index] -= taken;         // reduce the item's weight by the amount taken
    }
    return max_val;
}

Please review this code in terms of complexity or in other areas that might result in this code failing. Also, looking forward to criticism and if you decide to post criticism, kindly include relevant details that a not-so-experienced programmer might find helpful in solving the problem.

\$\endgroup\$
2
  • \$\begingroup\$ "in other areas that might result in this code failing" I assume you tested this though. How? Is the input sanitized or should any-and-all garbage be caught? \$\endgroup\$
    – Mast
    Commented Jul 7, 2019 at 8:01
  • \$\begingroup\$ @Mast This code is sanitised and I have verified it with multiple manual input tests. It works in all the test cases that I have found on the web and on those that I designed myself. However, I included your quoted phrase to signify that experienced coders might find out hidden bugs that only surface rarely and might cause the code to fail. \$\endgroup\$
    – gourabix
    Commented Jul 7, 2019 at 8:06

2 Answers 2

3
\$\begingroup\$

The algorithm

Your algorithm needs O(n) space (for storing all items), and O(n * k) time (for selecting the best ones) (n = items to choose from, k = items chosen, bounded by n).

By choosing as you go, you can get that down to O(k') space and O(n * k') time (k' = maximum items chosen at any time, at least k, bounded by n).

Take a look at std::push_heap, std::tuple and lambdas for implementing the new algorithm.

Avoid casting

Casting is error-prone, as it circumvents the protections of the type-system. Thus, use the most restricted cast you can, and don't cast at all if reasonably possible. In your case, why not multiply with 1.0 instead?

Floating-point is hard

You are calculating the specific value (value per weight) of your items for comparison purposes. Luckily, a double has enough precision that you are extremely unlikely to suffer from rounding-errors when dividing two 32 bit numbers. Still, instead of comparing 1.0 * a_value / a_weight < 1.0 * b_value / b_weight you could compare 1LL * a_value * b_weight < 1LL * b_value * a_weight, avoiding division and floating-point.

All those useless copies

While copying small trivial types is generally the right approach, a std::vector is neither small nor trivial; Copying it is rather expensive. If you only need to read it, use a constant reference or preferably a C++2a std::span for increased flexibility.

Gracefully handle all kinds of invalid input

No need to assume malice, you are assured your load of garbage anyway.

Just the code

  1. I don't see where you use anything from <cstdio>, so don't include it.

  2. Never import a namespace wholesale which isn't designed for it. Especially std is huge and ever-changing, which can silently change the meaning of your code even between minor revisions of your toolchain, let alone using a different one.
    It cannot be guaranteed to break noisily.

  3. return 0; is implicit for main(). Make of that what you will.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks for the tips! They are very useful and will help me improve my coding skills. However, I'm struggling to understand your intent in the Floating-point is hard section. I must calculate the maximum value per unit weight and then correspondingly select that item. I don't see how (long long)a_value * b_weight < (long long)b_value * a_weight helps. I'm most probably missing something. Could you help? \$\endgroup\$
    – gourabix
    Commented Jul 7, 2019 at 11:37
  • \$\begingroup\$ The point is that if you want to compare the specific value of two items, using floating point division is potentially inaccurate. The alternative I gave in contrast is guaranteed accurate if long long is at least twice as wide as int, which is likely. \$\endgroup\$ Commented Jul 7, 2019 at 11:40
  • \$\begingroup\$ But I would lose a lot of fractional digits (after the decimal point) with long long. That would be even less accurate than floating point division! \$\endgroup\$
    – gourabix
    Commented Jul 7, 2019 at 11:49
  • \$\begingroup\$ Your values and weights are integers, specifically int. As I only multiply and compare, and that with more doubled width, there is no decimal point introduced. \$\endgroup\$ Commented Jul 7, 2019 at 11:49
  • \$\begingroup\$ Yes, in that case, that's entirely correct. Thanks for the clarification! :) \$\endgroup\$
    – gourabix
    Commented Jul 7, 2019 at 11:51
2
\$\begingroup\$

1. Don't use using namespace std;

While that would work in your particular case, it's considered bad practice. Especially when you move out your code to separate header files.

See more details here please:

Why is “using namespace std;” considered bad practice?

2. Check for valid input

You don't check if input was valid here:

cout << "Enter the number of items: " << endl;
cin >> num_items;
cout << "Enter the total capacity that the bag can support: " << endl;
cin >> bag_capacity;

Rather use something like

std::cout << "Enter the number of items: " << std::endl;
while(!(cin >> num_items)) {
    std::cout << "Enter a valid number please." << std::endl;
    std::cout.clear();
    std::cout.ignore(std::limit::max);
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks fellow reviewer! (I wouldn't try to write your name). I'd definitely keep these points in mind. They are very helpful. \$\endgroup\$
    – gourabix
    Commented Jul 7, 2019 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.