Дробные рюкзаки с бахромой - PullRequest
Новая
       3

Дробные рюкзаки с бахромой

0 голосов
/ 05 февраля 2020

Я пытался решить проблему дробного ранца как часть учебника по жадному алгоритму. В следующем фрагменте ниже приведен мой код, и он, кажется, работает для базовых c случаев, поскольку я попытался выполнить несколько базовых c тестов, таких как выбор двух целых элементов, а затем выборка доли третьего вещь. Однако, когда я вводю его в набор тестов, этот алгоритм всегда не проходит тест.

Неудачный случай # 6/13: Получен неправильный ответ: 5810.101954463027 Ожидается: 7777.731

Я смотрел в коде, пытающемся выяснить, где находятся граничные случаи, когда он потерпел неудачу, и я ужасно потерпел неудачу в этом, поэтому я подумал, что некоторые свободные глаза помогут. Для справки, я добавляю алгоритм, который фактически передает граничные случаи ниже моего.

Мой алгоритм (не работает) 

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
  double value = 0;
  vector<double> valuePerWeight;

  // Populating an array called valuePerWeight with ratios of value:weight
  for (int i=0; i < weights.size(); i++) {
    double valueWeightRatio = values[i]/weights[i];
    valuePerWeight.push_back(valueWeightRatio);
  }

  // While there are still items to choose, and the bag is not full
  while (weights.size() > 0 && capacity > 0) {
    double max;
    int itemNum;

    // Going through every item, find the item with the highest valuePerWeight and record it
    for (int i=0; i < weights.size(); i++) {
      if (valuePerWeight[i] > max) { // If an item has been found to have a valuePerWeight greater than the previous max, update the new max and item number
        max = valuePerWeight[i];
        itemNum = i;
      }
    }

    // If there is enough space in the knapsack to put the item with the highest valuePerWeight
    if (capacity >= weights[itemNum]) {
      capacity = capacity - weights[itemNum]; // Adding it to the bag, and updating the capacity and value
      value = value + values[itemNum];

      // Removing the item from the arrays to ensure that it doesn't get picked again
      weights.erase(weights.begin() + itemNum);
      values.erase(values.begin() + itemNum);
      valuePerWeight.erase(valuePerWeight.begin() + itemNum);
      max = 0;
      itemNum = 0;
    }

    // If there isn't enough space in the knapsack to put the whole item with highest valuePerWeight in
    else if (capacity < weights[itemNum]) {

      // Calculate what fraction of the item can be put in
      double fraction = (double)capacity / (double)weights[itemNum];

      // Put in that fraction of the item and update the capacity and value
      value = value + (double)fraction*values[itemNum];
      capacity = capacity - (double)fraction*weights[itemNum];

      return value;
    }
  }

  return value;
}

Алгоритм, который работает 

int get_max_index (vector<int> weights, vector<int> values) {
    int max_i = 0; // index of the item with the highest value:weight ratio
    double max = 0; // the max value:weight ratio we've seen so far

    for (int i = 0; i < weights.size(); i++) { // iterating through the weights
        if (weights[i] != 0 && (double)values[i]/weights[i] > max) { // if the weights are not 0 and the value:weight ratio we've seen is the highest so far
            max = (double)values[i]/weights[i]; // update the max value
            max_i = i; // capture the index of the item with the highest value:weight ratio
        }
    }
    return max_i;
}

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
    double value = 0.0; // The answer to be returned, which is the value of the bag after putting all the items

    for (int i = 0; i < weights.size(); i++) { // Running this loop for every item in the bag
        if (capacity == 0) return value; // If the capacity of the bag has reached 0, return value
        int index = get_max_index(weights, values); // Get the index of the current item with the highest value:weight ratio
        int a = std::min(capacity, weights[index]); // Return the lower of the two: Remaining capacity of the bag or the weight of the item with the highest value:weight ratio
        value += a * (double)values[index]/weights[index]; // If there is sufficient capacity, put the whole item in, else, place a fraction of the item in: (capacity/weight)*value
        weights[index] -= a; // Update the item by removing it
        capacity -= a; // Update the capacity
    }

    return value;
}

1 Ответ

0 голосов
/ 05 февраля 2020

Я обнаружил проблему!

Я не приводил значение как двойное, и поэтому в тех случаях, когда соотношение значение: вес отличалось на незначительные величины, я ошибался.

Это изменение исправило алгоритм. 

  // Populating an array called valuePerWeight with ratios of value:weight
  for (int i=0; i < weights.size(); i++) {
    double valueWeightRatio = (double)values[i]/weights[i];
    valuePerWeight.push_back(valueWeightRatio);
  }
...