knapsack with weight only

Viewed 12120

if i had given the maximum weight say w=20 .and i had given a set on weights say m=[5,7,12,18] then how could i calculate the max possible weight that we can hold inside the maximum weight using the m. in this case the answer is 19.by adding 12+7=19. and my code is giving me 18.please help me in this.

int weight(int W, vector<int> &m) {

  int current_weight = 0;
  int temp;
  for (int i = 0; i < w.size(); i++) {
    for (int j = i + 1; j < m.size(); j++) {
      if (m[i] < m[j]) {
        temp = m[j];
        m[j] = m[i];
        m[i] = temp;
        }
      }
    }

  for (size_t i = 0; i < m.size(); ++i) {
    if (current_weight + m[i] <= W) {
       current_weight += m[i];
      }
    }
 
  return current_weight;
  }
2 Answers

So it feels like this solution can be a trivial change to the commonly existing 0-1 knapsack problem, by passing the copy of the weight array as the value array.

Related