Итоговый вес в ранце 0: 1?

Как найти окончательный вес оптимального набора решения DP задачи 0-1? Дан набор из n элементов, каждый из которых имеет свой вес и ценность.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

vector < pair <int, int> > arr;
map < pair <int, int>, int > hash_memo;
pair <int, int> temp;

int knapsack(int N, int budget)
{
    int a, b=0;
    pair <int, int> local;
    if((!N) || (!budget)) return 0;
    local.first = N;
    local.second = budget;
    if(hash_memo[local]) return hash_memo[local];

    a = knapsack(N-1, budget);
    if(budget >= arr[N-1].first)
    {
        b =  arr[N-1].second + knapsack(N-1, budget - arr[N-1].first);
    }

    if(a>b)
    {
        hash_memo[local] = a;
        return a; 
    }
    hash_memo[local] = b;
    return b;
}

int main()
{
int budget, N, a, b;

    while(1)
    {
        scanf("%d %d", &budget, &N);
        if((!budget) && (!N)) break;

        arr.clear();
        hash_memo.clear();
        for(int i=0; i<N; i++)
        {
            scanf("%d %d", &a, &b);
            if(b==0) continue;
            temp.first = a; temp.second = b;
            arr.push_back(temp);
        }

        int max_value = knapsack(N, budget);
        printf("%d\n", max_value);
    }

return 0;
}

Выше приведен код для задачи о рюкзаке 0-1, где max_value дает окончательное значение оптимального набора. Как узнать «максимальный_вес»? «N» - это количество предметов, «бюджет» - это максимальный вес, который можно учитывать.


algorithm knapsack-problem dynamic-programming
person ashrithhcs    schedule 24.05.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Верните пару значений, содержащих вес и значение:

pair<int, int> knapsack(int N, int budget)
{
    if((!N) || (!budget)) return pair<int, int>(0, 0);

    pair<int, int> local(N, budget);
    if(hash_memo[local].second) return hash_memo[local];

    pair<int, int> b = pair<int, int>(0, 0);
    pair<int, int> a = knapsack(N-1, budget);
    if(budget >= arr[N-1].first)
    {
        pair<int, int> c = knapsack(N-1, budget - arr[N-1].first);
        b = pair<int, int>(c.first + arr[N-1].first, c.second + arr[N-1].second);
    }

    if(a.second > b.second)
    {
        return hash_memo[local] = a;
    }
    return hash_memo[local] = b;
}
person fgb    schedule 25.05.2014
comment
Из этого ответа я узнал кое-что очень новое. Очень аккуратная модификация моего фрагмента кода. Большое спасибо. Большая помощь :) - person ashrithhcs; 26.05.2014