Извлечение предметов из рюкзака с помощью динамического программирования

Я новичок в динамическом программировании и попробовал свою первую проблему DP. Постановка проблемы

Учитывая рюкзак размера C и n предметов размеров s[] со значениями v[], максимизируйте вместимость предметов, которые можно положить в рюкзак. Элемент может повторяться любое количество раз. (Допускается дублирование элементов).

Хотя я смог сформулировать рекуррентное соотношение и создать таблицу DP и, в конечном итоге, получить максимальное значение, которое можно положить в рюкзак, я не могу найти метод, чтобы получить, какие значения нужно выбрать, чтобы получить требуемую сумму. .

Вот мое решение:

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int s[] = { 1, 3, 4, 5, 2, 7, 8 , 10};
    int v[] = { 34, 45, 23, 78, 33, 5, 7 , 1};
    int n = ( (sizeof(s)) / (sizeof(s[0])) );
    vector<int> backtrack;
    int C = 15;
    int pos;
    int m[20];
    m[0] = 0;
    int mx = 0;
    for ( int j = 1; j <= C; j++) {
        mx = 0;
        m[j] = m[j-1];
        pos = j-1;  
        for ( int i = 0; i < n; i++) {
            mx = m[i-s[i]] + v[i];
            if ( mx > m[i] ) {
                m[i] = mx;
                pos = i - s[j];
            }
        }   
        backtrack.push_back(pos);
    }
    cout << m[C] << endl<<endl;
    for ( int i = 0; i < backtrack.size(); i++) {
        cout << s[backtrack[i]]  <<endl;
    }   
    return 0;
}

В своем решении я попытался сохранить позиции элемента с максимальным значением, выбранным в векторе, и в конечном итоге распечатать их. Однако это, похоже, не дает мне правильного решения.

Запуск программы производит:

79

2
3
0
5
2
7
8
10
34
45
23
78
33
5
7

Из вывода очевидно, что числа в выводе не могут быть размерами выбранных элементов, поскольку нет элемента размера 0, как показано в выводе.

Я надеюсь, что вы поможете мне найти ошибку в моей логике или реализации. Спасибо.


c++ recurrence knapsack-problem dynamic-programming
person user1043884    schedule 29.06.2012    source источник
comment
@PeeWee2201: Обратите внимание, что это не домашнее задание. Если бы это был один, я бы пометил его соответствующим образом. Мне очень жаль, что даже набрав вопрос через час (поскольку английский не мой родной язык), вы сочли его домашним заданием. Я сожалею, что побеспокоил вас своим домашним заданием, похожим на вопрос. Извините еще раз.   -  person user1043884    schedule 29.06.2012
comment
Очевидно, что в вашем коде есть проблема с выходом за пределы массива. Например, в операторе mx = m[i-s[i]] + v[i] индекс m будет равен -1, когда i = 0, а pos = i - s[j] также выйдет за пределы, когда j >= n.   -  person Anders Gustafsson    schedule 29.06.2012

Ответы (1)


arrow_upward
0
arrow_downward

Вы следуете жадному подходу. Это довольно умно, но эвристично. Я не буду давать вам правильный код, так как это может быть домашним заданием, но рекурсивная функция knapsack будет выглядеть так:

knapsack(C): maximum profit achivable using a knapsack of Capacity C
knapsack(C) = max { knapsack(C-w[i]) + v[i] } for all w[i] <= C
knapsack(0) = 0

В коде:

dp(0) = 0;
for i = 1 to C
  dp(i) = -INF;
  for k = i-1 downto 0
     if w[k] < i then
        dp(i) = max{dp(i-w[k]) + v[k], dp(i)};
print dp(Capacity);
person Rontogiannis Aristofanis    schedule 29.06.2012