背包问题

简单粗暴的解决背包问题

#include "pch.h"
#include <iostream>
#include <vector>
#include <map>
#include <time.h>

struct Item {
    int id;
    int value;
    int space;
};

std::vector<std::vector<int>> GetAllCombines(const std::vector<int>& items) {
    std::vector<std::vector<int>> ret;
    if (items.size() == 1) {
        ret.push_back(items);
        return ret;
    }

    std::vector<int> prev_items(items);
    auto last_item = prev_items.back();
    prev_items.pop_back();
    auto prev = GetAllCombines(prev_items);
    
    for (auto& i : prev) {
        ret.push_back(i);

        auto j(i);
        j.push_back(last_item);
        ret.push_back(j);
    }

    std::vector<int> temp;
    temp.push_back(last_item);
    ret.push_back(temp);
    return ret;
}

std::vector<int> GetMaxValueItems(int total_space, const std::map<int, Item>& items) {
    int max_value = 0;
    std::vector<int> ret;

    std::vector<int> vec_items;
    for (auto it : items) {
        vec_items.push_back(it.first);
    }
    
    std::vector<std::vector<int>> all_combines = GetAllCombines(vec_items);
    for (size_t i = 0; i < all_combines.size(); i++) {
        int cur_value = 0;
        int cur_space = 0;
        const auto& this_combine = all_combines[i];
        for (auto item_id : this_combine) {
            auto it = items.find(item_id);
            if (it == items.end())
                return std::vector<int>();
            auto& item = it->second;
            cur_value += item.value;
            cur_space += item.space;

            if (cur_space > total_space) {
                break;
            }
        }

        if (cur_space > total_space) {
            continue;
        }

        if (cur_value > max_value) {
            max_value = cur_value;
            ret = this_combine;
        }
    }

    return ret;
}

int main()
{
    srand(time(nullptr));

    std::map<int, Item> items;
    for (int i = 0; i < 20; i++) {
        Item item;
        item.id = i + 1;
        item.space = rand() % 8;
        item.value = rand() % 32;
        items[item.id] = item;
    }

    auto ret = GetMaxValueItems(10, items);
    return 0;
}

性价比排序解决背包问题

#include "pch.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <time.h>

struct Item {
    int id;
    int value;
    int space;

    bool IsMoreValue(const Item& b) const {
        if (space == 0) {
            if (b.space == 0)
                return value > b.value;
            else
                return true;
        }

        float fValue = float(value) / space;
        float fBValue = float(b.value) / b.space;
        return fValue > fBValue;
    }
};

bool Compare(const Item& a, const Item& b) {
    if (a.IsMoreValue(b))
        return true;
    else
        return false;
}

std::vector<int> GetMaxValueItems(int total_space, const std::map<int, Item>& items) {
    std::vector<Item> vec_items;
    for (auto it : items) {
        vec_items.push_back(it.second);
    }

    std::sort(vec_items.begin(), vec_items.end(), Compare);

    int cur_space = 0;
    std::vector<int> ret;

    for (size_t i = 0; i < vec_items.size(); i++) {
        auto& item = vec_items[i];
        if (cur_space + item.space > total_space) {
            break;
        }

        cur_space += item.space;
        ret.push_back(item.id);
    }

    return ret;
}

int main()
{
    srand(time(nullptr));

    std::map<int, Item> items;
    for (int i = 0; i < 20; i++) {
        Item item;
        item.id = i + 1;
        item.space = rand() % 8;
        item.value = rand() % 32;
        items[item.id] = item;
    }

    auto ret = GetMaxValueItems(10, items);
    return 0;
}