Решение рюкзака с использованием рекурсивного алгоритма

Question

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

Я написал:

// Knapsack_memoryfunc.cpp : Defines the entry point for the console application. 
//Solving Knapsack problem using dynamic programmig and Memory function 

#include "stdafx.h" 
#include "iostream" 
#include "iomanip" 
using namespace std; 

int table[20][20] = { 0 }; 
int value, n, wt[20], val[20], max_wt; 

// ---CONCERNED FUNCTION----- 

int MNSack(int i, int j) 
{ 
    value = 0; 
    if (table[i][j] < 0) 
     if (j < wt[i]) 
      value = MNSack(i - 1, j); 
     else 
      value = fmax(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i])); 

    table[i][j] = value; 
    return table[i][j]; 
} 

// -------------------------- 

void items_picked(int n, int max_wt) 
{ 
    cout << "\n Items picked : " << endl; 
    while (n > 0) 
    { 
     if (table[n][max_wt] == table[n - 1][max_wt]) // if value doesnot change in table column-wise, item isn't selected 
      n--;          // n-- goes to next item 
     else           // if it changes, it is selected 
     { 
      cout << " Item " << n << endl; 
      max_wt -= wt[n];       // removing weight from total available (max_wt) 
      n--;          // next item 
     } 
    } 
} 

int main() 
{ 

    cout << " Enter the number of items : "; 
    cin >> n; 
    cout << " Enter the Maximum weight : "; 
    cin >> max_wt; 
    cout << endl; 
    for (int i = 1; i <= n; i++) 
    { 
     cout << " Enter weight and value of item " << i << " : "; 
     cin >> wt[i] >> val[i]; 
    } 

    for (int i = 0; i <= n; i++) 
     for (int j = 0; j <= max_wt; j++) 
      table[i][j] = 0; 

    for (int i = 1; i <= n; i++) 
     for (int j = 1; j <= max_wt; j++) 
      table[i][j] = -1; 

    cout << " Optimum value : " << MNSack(n, max_wt); 

    cout << " \n Table : \n"; 
    for (int i = 0; i <= n; i++) 
    { 
     for (int j = 0; j <= max_wt; j++) 
      if (table[i][j] == -1) 
       cout << setw(5) << "-"; 
      else 
       cout << setw(5) << table[i][j]; 
     cout << endl; 
    } 

    items_picked(n, max_wt); 


    return 0; 
} 

Вот вопрос и выход:

Похоже, его правильно на некоторых местах, как оптимальное значение, но не полностью приемлемый. Я пытался отладить его, но его довольно сложно с рекурсивными функциями. Кто-то может помочь?

Answer 1

int MNSack(int i, int j) 
{ 
    value = 0; 
    if (table[i][j] < 0) 
    { 
     if (j < wt[i]) 
      value = MNSack(i - 1, j); 
     else 
      value = max(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i])); 

     table[i][j] = value; 
    } 
    return table[i][j]; 
} 

Проблема возникает здесь. Когда ваш элемент таблицы больше или равен 0, вы пропустите рекурсию, но все равно установите для элемента таблицы значение 0, что будет неправильным, если ваш элемент таблицы больше 0.

Вам нужно только обновить когда он должен быть изменен, поэтому поместите его в скобки, это исправит.

Answer 2

Нижнее решение.

#include <iostream> 
#include <algorithm> 
#include <iomanip> 
using namespace std; 


int main() 
{ 
    int table[20][20] = { 0 }; 
    int value, n, wt[20], val[20], max_wt; 

    cout << " Enter the number of items : "; 
    cin >> n; 
    cout << " Enter the Maximum weight : "; 
    cin >> max_wt; 
    cout << endl; 
    for (int i = 1; i <= n; i++) 
    { 
     cout << " Enter weight and value of item " << i << " : "; 
     cin >> wt[i] >> val[i]; 
    } 

    // Initialization 
    for (int i = 0; i <= n; i++) 
     for (int j = 0; j <= max_wt; j++) 
      table[i][j] = 0; 

    // In practice, this can be skipped in a bottom up solution 
    for (int i = 1; i <= n; i++) 
     for (int j = 1; j <= max_wt; j++) 
      table[i][j] = -1; 

    for (int i = 1; i <= n; i++) 
    { 
     for (int j = 1; j <= max_wt; j++) 
     { 
      if (j < wt[i]) 
       table[i][j] = table[i - 1][j]; 
      else 
       table[i][j] = max(table[i - 1][j], val[i] + table[i - 1][j - wt[i]]); 
     } 
    } 

    cout << " Optimum value : " << table[n][max_wt] << endl; 

    cout << " \n Table : \n"; 
    for (int i = 0; i <= n; i++) 
    { 
     for (int j = 0; j <= max_wt; j++) 
      if (table[i][j] == -1) 
       cout << setw(5) << "-"; 
      else 
       cout << setw(5) << table[i][j]; 
     cout << endl; 
    } 

    return 0; 
} 

Вы можете видеть, что это изменяет рекурсию на цикл и, следовательно, позволяет избежать глобальных переменных. Это также упрощает код, поэтому вы можете не проверять, действителен ли элемент таблицы (равный -1 в вашем примере).

Недостатком этого решения является то, что он всегда пересекает все возможные узлы. Но он получает лучший коэффициент за элемент, потому что рекурсия и двойная проверка элемента таблицы стоят дороже. Как сверху вниз, так и снизу вверх имеют одинаковый порядок сложности O (n^2), и трудно сказать, какой из них быстрее.