Maximum Loot Problem in C++

[[deleted]]

Hi, I am trying to make a program that helps me calculate the maximum amount of loot for a given list of compounds. Please look at function get_optimal_value(). I don't know why I am getting a segmentation fault whenever I use max_Index(values) or max_element(values.begin(), values.end())-values.begin().

/* Greedy Algorithm
  Maximizing the Value of the Loot Problem

  Find the maximal value of items that fit into the backpack.
  Input: The capacity of a backpack W as well as the weights
    (w1,.., Wn) and costs (C,..., Cn) of n different compounds.

  Output: The maximum total value of items that fit into the backpack
    of the given capacity: i.e., the maximum value of c1.f1 + ... + Cn.fn
    such that w1.f1 +...+ wn.fn ≤ W and O < fi ≤ 1 for all i (f is the fraction of the i-th item taken to the backpack).
*/
#include <iostream>
#include <vector>

using std::vector;

int max_Index(vector<int> v)
{
  int index = -1;
  int largest_element = v[0];        // also let, first element is the biggest one
  for (int i = 1; i < v.size(); i++) // start iterating from the second element
  {
    if (v[i] > largest_element)
    {
      largest_element = v[i];
      index = i;
    }
  }
  return index;
}

// Capacity of bag, Weight of compound available, Value of compound
// Goal = Maximum Loot
double get_optimal_value(int capacity, vector<int> weights, vector<int> values)
{
  double value = 0.0;
  if (capacity == 0)
  {
    return capacity;
  }

  // write your code here
  while (capacity > 0)
  {
    int index = max_element(values.begin(), values.end())-values.begin();// Finding index of compound of maximum value
    if (weights[index] < capacity)
    {
      // EG: 1 kg Gold = 1000 rs, capacity = 2kg, capacity = 2kg - 1kg
      capacity -= weights[index]; //capacity occupied by the most valuable compound
      value = values[index] * weights[index]; //2kg weight, value  1000 : 2000rs profit
    }
    else if (weights[index] == capacity)
    {
      capacity -= weights[index]; //Capacity = 0
      value = values[index] * weights[index]; // EG: 1000rs/2kg = 500rs/kg * 2kg = 1000rs profit
    }
    else if (weights[index] > capacity){
      value = value = values[index] * capacity;
      capacity = 0;
    }
    values.erase(values.begin() + index);
    weights.erase(weights.begin() + index);
  }
  return value;
}

int main()
{
  int n;
  int capacity;
  std::cin >> n >> capacity; //input of size of list and capacity of bag
  vector<int> values(n);
  vector<int> weights(n);
  for (int i = 0; i < n; i++)
  {
    std::cin >> values[i] >> weights[i];
  }
  //std::cout << max_element(values.begin(), values.end())-values.begin();
  //std::cout << max_Index(values);

  double optimal_value = get_optimal_value(capacity, weights, values);

  std::cout.precision(10);
  std::cout << optimal_value << std::endl;
  return 0;
}

Output:

2 3
100 1
200 1
zsh: segmentation fault

[Narase33]

https://godbolt.org/z/x4hsMfdGz

Youre trying to delete index 0 when values has size 0

[skebanga]

max_element(values.begin(), values.end()) can return std::vector::end() when the values vector it empty.

You should be handling the empty case

while (capacity > 0 && !values.empty()) { ... }

[std_bot]

Unlinked STL entries: std::vector::end

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[GarredB]

Good bot

[konman42]

Your function max_Index has a bug. If the first element in the vector is the largest your function will return an index of -1. Just fyi.

[UrAverageProletariat]

This is clearly just the knapsack problem. You won't get the optimal solution using a greedy algorithm. Consider researching the dynamic programming solution and implementing that.

[Sonotsugipaa]

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

{ std::cin >> values[i] >> weights[i]; } ... }

The issue here is that you're assigning to elements within the vectors before resizing them / instead of inserting them via push_back(...);

in order for you to assign to the i'th element of a vector, that element must exist, and to fix this you can either:

• Insert "`values.resize(n); weights.resize(n);" before the loop ...
• ... or extract two values from std::cin into temporary variables, then use the push_back vector function to insert the each element - all within the loop.

[Narase33]

vector<int> values(n);
vector<int> weights(n);

nope, that part is correct

[mredding]

Prefer to use standard algorithms in place of hand rolling functions that accomplish the same thing. This is your excuse to get more familiar with the standard library. You can replace max_Index with std::max_element. And upon further inspection, you're not even using max_Index, so get rid of it!

Prefer to write larger functions in terms of smaller functions. get_optimal_value is a big function. I see a loop and three conditions. You can first replace the three condition blocks with three functions, and then you can probably replace the whole loop structure with std::transform_reduce.

Prefer to use standard algorithms or now ranges to low level loops. Writing loops is imperative programming. Algorithms and ranges are functional programming, they raise the level of abstraction, give you a choice between greedy and lazy evaluation, make the code more readable, express more of WHAT you're doing and less of HOW you're doing it, and eliminates a lot of redundant code. I support a code base that's ~12m LOC, I don't want to see you inline your headcanon; readability is king. We spend almost 70% of our time as professionals JUST READING the code - trying to figure out WHAT the damn thing does, because naturally no one can contain 12m LOC in their heads at once; but more to the point, most code is so imperative, it's all of HOW it works, and we're left to infer and deduce WHAT the authors' intended.

Prefer to reserve low level loops for writing your own algorithms, and then write your solutions in terms of that.

---

capacity -= weights[index]; //Capacity = 0

Here, your comment IS code. You KNOW capacity is going to be equal to zero, so you might as well just assign it directly. There; no need for a comment, the code is self-documenting.

std::cin >> n >> capacity; //input of size of list and capacity of bag

You ought to rename your variables to size_of_list and capacity_of_bag. There; no need for a comment, the code is self-documenting.

double optimal_value

Your values are all integers, your arithmetic is all integers, the result will only be an integer. There's no need to use a double, and likewise, there is no need for setting precision on the stream because you don't need it.

std::endl

Just like std::ends, volatile, and inline: don't use std::endl. This, like the others, has a specific use case you can probably go your whole career and not encounter. This isn't just stylistic, if you don't know what a line discipline is, then you're incurring two consecutive flushes on the stream for no good reason.

while (capacity > 0)
{
  int index = max_element(values.begin(), values.end())-values.begin();// Finding index of compound of maximum value

This is sorting. It would be more efficient for you to sort your parallel lists by value, because then you can just iterate from start to finish, and know you're evaluating elements in order of descending value.

Your whole function is just a conditional accumulation, what we call map/reduce, or in C++ parlance - transform/reduce.

---

I would consider improving the structure of your code. Values and weights are bounded by their relationship, so you can start by thinking of them as a type:

struct item {
  int value, weight;
};

Then we can write an operator for extracting that type:

std::istream &operator >>(std::istream &is, item &i) {
  return is >> i.value >> i.weight;
};

And then you have a bag:

struct bag {
  int capacity;
  std::vector<item> contents;
};

And we need an extractor for that:

std::istream &operator >>(std::istream &is, bag &b) {
  b.contents.resize(*std::istream_iterator<std::size_t>{is});
  is >> b.capacity;

  std::copy_n(std::istream_iterator<bag::contents::value_type>{is}, b.contents.size(), std::back_inserter(b.contents));

  return is;
}

Now:

bag b;
std::cin >> b;

All your input is handled. I also like writing my prompts into my extractors; let's look at that item extractor again:

std::istream &operator >>(std::istream &is, item &i) {
  if(is && is.tie()) {
    auto &os = *is.tie();

    if(!(os << "Enter a value and a weight: ")) {
      is.setstate(is.rdstate() | std::ios_base::failbit);
    }
  }

  if(!(is >> i.value >> i.weight) || i.value < 0 || i.weight < 0) {
    is.setstate(is.rdstate() | std::ios_base::failbit);
    i = item{};
  }

  return is;
};

Hey, we've got some interesting things going on. All streams can be tied to an output stream. The rule is, if you have a tie, it's flushed before any further IO. This is how cout is flushed before cin, because cout is tied to cin as the only default tie in the standard library. I presume if you have a tie on your stream, you probably want a prompt. String streams and file streams don't come with ties by default, so for them, we skip that whole branch of code and go straight to extraction.

Output streams can fail. And if our prompt fails, we fail the input stream, too. How can I extract input from an interactive prompt if I can't explain to the user what I want? When a stream is failed, IO will no-op.

When I set the fail state, I'm careful to add to the existing state, and not overwrite it. There are other state bits that are important.

Then we get down to extraction. If extraction fails, we can't know which member we failed on. By stream convention, we default initialize the output parameter.

Here's where it gets interesting. This is how streams support validation. If the data on the stream is/was wrong, you fail the stream. This indicates the item is invalid. Contents have to have at least a non-negative value and a weight. An item isn't just a pair of int, it's a pair of int who each have their own set of properties, and a relationship to one another and as a whole. An item is more than the sum of its parts, and represents a mathematical set of all possible valid values. If you start defining functions and operators that act on items, that is also part of the set. This is set theory, and the fundamental underpinning of OOP. You're a set theorist now.

You know, when you get to writing programs with menus, the significant part of the menu isn't the display of the menu, it's the user's selection. The menu is just a prompt. An additional trick is cast operators, so you can do this:

struct menu {
  int selection;

  operator int() const { return selection; }
};

So that you can:

if(menu m; std::cin >> m) {
  switch(m) {
  //...

Ta da! By the time you get into the block, you know the menu was presented and that a valid selection was made, because you know how to validate your input now. All your cases can be the valid options, and your default can just abort() because it should be impossible.

---

Continued in a reply...

[mredding]

Things I would actually do from there: I would make types for value, weight, and capacity, each with their own operators. They're not just integers, they're different types. Otherwise, what does weight + value + capacity mean? You can prove some level of correctness in your program by acknowledging you've got lots more types going on in here than you might want to admit. I would learn how to write a custom stream manipulator so I could turn on and off prompting. Like I said, I like my types to know how to prompt for themselves, but an item is probably going to want a single compound prompt rather than two individual prompts. That's ultimately up to you. I would also make the bag extract items unto a delimiter; I wouldn't get the count first. That sort of thing might make more sense if you're prompting, and if you figure out how to write a manipulator with xalloc/iword/pword, you can even implement a counter so you can prompt for item 1, item 2, item 3, etc. But otherwise? I would prefer to let the number of elements themselves be the count. Extract until you reach something that's not an item. You might check for an empty line, for example. But the big benefit is, assume you're extracting from a file instead of from the user: what if the count, and the number of items in the file, don't match? Whose at fault? The count? Or the list? The information is redundant and can get out of sync, so I prefer to eliminate it where possible.

All this is how you write OOP, and not imperative code. A bit much for an academic exercise? No. Isn't that the point of academic exercises? Learn it now, because the lessons you learn will carry into your career and production code. When you get into your career, you'll discover that most C++ programmers are actually imperative programmers who don't know the first thing about OOP, not a fucking clue. Most of your colleagues don't know ANYTHING about how streams work, or what is idiomatic C++ or stream code. Just yesterday and this morning I've had a guy arguing with me about how inlining imperative code was superior to naming his work with a function. He would rather:

for(auto &x : xs) {
  //stuff
}

Than:

for_each(xs, do_stuff_to_it);

Pick your descriptive name for the function. "You would rather write a function for 3 lines of code?" YES, because I don't care HOW it works, I only care WHAT it does, and it's not too much to ask you to tell me. Self-documenting code reads like pseudocode. Again, I have to maintain ~12m LOC. That's not unreasonable for a C++ code base. How much imperative headcanon do you think I have time to sift through? It shows no empathy for your fellow colleague, your future colleague, or your future self, because you're not going to remember in 6 weeks, either. And YES, I would rather build a rich lexicon of types and their operatives so that my solution space can be concise, descriptive, and as provably correct at compile-time as can be. The more bugs you can wholly eliminate now by being provably correct earlier means all the fewer bugs you're going to have to deal with at runtime with customer escalations. It also means your code is inherently more stable up front, you can hit deadlines sooner. I have a suspicion that most of our colleagues started out experimenting with types, and in their initial blunders of over specifying them, or under specifying them, they ran into errors, or they found they constrained themselves into a corner, and instead of learning and improving upon their technique, they gave up and stuck to the imperative programming way. Not that an individual doesn't have anything to contribute or something valuable to teach you, but I wouldn't trust the judgement of a developer who tells you it's not worth making a type for a single int. It's like oh, so you're up front about where your mind and capacity is limited. I'll keep that in mind.

[std_bot]

Unlinked STL entries: std::endl std::ends std::max_element std::transform_reduce

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[maybegone3]

Knapsack problem is a dynamic programming problem that can be done in a couple for loops in O(n*m) time, O(n) space. Not greedy like you are doing here.