Özyinelemeli algoritma kullanarak Sırt Çantası Çözümü

Question

Bu algoritmayı ders kitabımızdan uygulamaya çalışıyorum. Henüz,

Optimum değer gibi bazı yerlerde onun doğru gibi görünüyor değildir: Burada

// 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; 
} 

soru çıktısı:

Bunu yazdım tamamen kabul edilebilir. Hata ayıklamayı denedim, ancak özyinelemeli işlevleri ile oldukça zor. Birisi lütfen yardım edebilir mi?

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]; 
} 

Sorun burada gelir. Tablo öğeniz daha büyük veya 0'a eşit olduğunda, yinelemeyi atlarsınız ancak tablo öğenizi 0'dan büyükse, yine de tablo öğesini 0'a ayarlayacaksınız.

Sadece güncelleştirmeniz gereken Tablo öğesinde değişiklik olması gerektiğinde, bunu düzeltmek için parantez içine koyun.

Answer 2

Aşağıdan yukarıya çözüm.

#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; 
} 

Bunun yinelemeyi döngü olarak değiştirdiğini ve dolayısıyla genel değişkenleri önlediğini görebilirsiniz. Ayrıca kodu kolaylaştırır, böylece tablo öğesinin geçerli olup olmadığını kontrol etmekten kaçınabilirsiniz (örneğinizde -1'e eşittir).

Bu çözümün dezavantajı, her zaman olası tüm düğümleri geçmesidir. Ancak, özü ve tablo öğesinin iki kez kontrol edilmesi daha fazla maliyete sahip olduğundan, öğe başına daha iyi katsayı kazanır. Hem yukarıdan aşağıya hem de aşağıdan yukarıya aynı karmaşıklık derecesine sahip O (n^2), hangisinin daha hızlı olduğunu söylemek zor.