分数背包流苏案例

Question

作为贪心算法教程的一部分，我一直在尝试解决小数背包问题。下面的代码片段是我的代码，它似乎适用于基本情况，因为我已经尝试了运行一些基本测试，例如必须选择两个完整的项目，然后选择第三个项目的一小部分。但是，当我把它输入到测试套件中时，这个算法总是测试失败。

失败案例 #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;
}

Answer 1

我找到问题了！

我没有将值转换为双精度值，因此在 value:weight 比率相差极小的情况下，我弄错了。

此更改修复了算法。

  // 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);
  }

分数背包流苏案例

Fractional Knapsack fringe cases

c++

greedy