Как отсортировать вектор возможностей в задаче о ранце 0/1, используя шаблонную функцию min_max, которую я написал? - PullRequest
Новая
       25

Как отсортировать вектор возможностей в задаче о ранце 0/1, используя шаблонную функцию min_max, которую я написал?

1 голос
/ 29 марта 2020

У SO уже есть несколько вопросов, связанных с этим топи c. Мой вопрос не об алгоритме. Это сортировка итогового вектора possibilities по прибыли

. Я написал следующий фрагмент кода для решения проблемы ранца 0/1: 

#include "algorithms.h"

struct Item {
    int index = 1;
    int profit = 1;
    int weight = 1;
    Item() = delete;
    explicit Item(int i, int _profit, int w) {
        index = i;
        profit = _profit;
        weight = w;
    }
    bool operator<(const Item& item) {
        return this->profit < item.profit;
    }
    bool operator<=(const Item& item) {
        return this->profit <= item.profit;
    }
    bool operator>(const Item& item) {
        return this->profit > item.profit;
    }
    bool operator>=(const Item& item) {
        return this->profit >= item.profit;
    }
    friend std::ostream& operator<<(std::ostream& out, const Item item) {
        out << item.index;
        return out;
    }
};

long weight(const std::vector<Item>& item_list, const std::vector<int>& item_switch) {
    long sum = 0;
    for (int i = 0; i < item_switch.size(); i++) {
        sum += item_switch[i] * item_list[i].weight;
    }
    return sum;
}

void increment(std::vector<int>& vec) {
    auto it_bit = vec.end();
    it_bit--;
    while (*it_bit == 1) {
        *it_bit = 0;
        if (it_bit == vec.begin()) {
            return;
        }
        it_bit--;
    }
    *it_bit = 1;
}

int main() {
    long M = 25;
    Item i1(1, 10, 9);
    Item i2(2, 12, 8);
    Item i3(3, 14, 12);
    Item i4(4, 16, 14);
    std::vector<Item> items = { i1,i2,i3,i4 };
    std::vector<int> enable(4,0);
    std::vector<std::vector<int>> possible;
    for (int i = 1; i <= 16; i++) {
        if (weight(items, enable) <= M) {
            possible.push_back(enable);
        }
        increment(enable);
    }
    for (const auto& vec : possible) {
        for (const auto& num : vec) {
            std::cout << num << " ";
        }
        std::endl(std::cout);
    }
    return 0;
}

Как видите, я реализован вектор possibilities, который по существу является вектором, обозначающим присутствие possibilities[index] numbered item, делая этот бит 1, т.е. 1010 означает, что присутствуют объекты 1 и 3. Я не могу придумать хороший лог c, чтобы найти возможность с максимальной вероятностью функцией min_max, которую я написал как шаблон здесь . Пожалуйста, помогите.

Логи c Я использовал: 

long profit(const std::vector<Item>& item_list, const std::vector<int>& item_switch) {
    long sum = 0;
    for (int i = 0; i < item_switch.size(); i++) {
        sum += item_switch[i] * item_list[i].profit;
    }
    return sum;
}

На основном: 

long pr = 0;
for (int i = 0; i < possible.size(); i++) {
    long temp = profit(items, possible[i]);
    if (temp > pr) {
        pr = temp;
    }
}

Также название вопроса открыто для предложений ?

...