Рюкзак DP Как узнать общее количество взятой стоимости? - PullRequest
Новая
       10

Рюкзак DP Как узнать общее количество взятой стоимости?

0 голосов
/ 16 декабря 2011

Это как

Максимальный вес 3 

Value Weight 

1955    1
2000    5
101     1

Возьмите первое и третье. но не могу найти, чтобы найти общую стоимость. 1955 + 101

я использую рюкзак 0-1. есть ли вообще найти 1955 + 101 из массива

1 Ответ

0 голосов
/ 19 декабря 2011

Допустим, у вас есть 2 массива значений и wt и еще одна переменная initial_capacity , котораямаксимальная вместимость рюкзака.Затем вам сначала нужно вызвать функцию dp , которая вычисляет maxValue , которого вы можете достичь.Функция реконструкция сообщает, какие предметы вы должны взять для достижения maxValue. 

int dp(int position, int weight)
{
    if(position == no_of_items) return 0;
    if(mem[position][weight] != -1) return mem[position][weight];

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    return mem[position][weight] = max(r1, r2);
}

void reconstruct(int position, int weight)
{
    if(position == no_of_items) return;

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    if(r2 > r1)
    {
        cout << "Take item at position : " << position << endl;
        reconstruct(position + 1, weight - wt[position]);
    }
    else
    {
        reconstruct(position + 1, weight);
    }
}

int main()
{
    //read input here
    memset(mem, -1);
    int maxValue = dp(0, initial_capacity);
    cout << "Max value : " << maxValue << endl;
    reconstruct(0, initial_capacity);
}

Обратите внимание, что реконструкция работает жадным образом.Какое бы решение (взять или пропустить элемент) привело к maxValue, оно примет это решение.Если ваше решение связано с получением определенного предмета, вы распечатываете индекс этого предмета.

Надеюсь, это поможет:)

...