Реализация Knapstack на c ++ с использованием мемоизации - PullRequest
Новая
       41

Реализация Knapstack на c ++ с использованием мемоизации

0 голосов
/ 28 мая 2020

В чем разница между выполнением int t[102][1002] = {-1}; и запуском для l oop и выполнением 

for(int i = 0; i < 102; i++)
        for(int j = 0; j < 1002; j++)
            t[i][j] = -1;

Приведенный ниже код не работает при использовании первого метода. Это работает только тогда, когда мы l oop через и инициализируем. Почему? 

#include<bits/stdc++.h>
using namespace std;
int t[102][1002] = {-1};
int knapstack(int wt[], int val[], int w, int n)
{
    if(n == 0 || w == 0)
        return 0;

    if (t[n][w] != -1)
        return t[n][w];

    if(wt[n-1] <= w ){
        t[n][w] = max(val[n-1] + knapstack(wt,val, w - wt[n-1],n-1) , knapstack(wt, val, w, n-1));
        return t[n][w];
    }

    if(wt[n-1] > w){
       t[n][w] = knapstack(wt,val,w,n-1); 
       return t[n][w];
    }
}

int main()
{
    int wt[] = {10, 20, 30};
    int val[] = { 60, 100, 120};
    int w = 50, n = sizeof(val)/sizeof(val[0]);
    cout<< knapstack(wt, val, w, n);
}

Ответы [ 2 ]

1 голос
/ 28 мая 2020

это устанавливает только первую ячейку 2D-массива t в -1. 

int t[102][1002] = {-1};

Лучше использовать любой из этих двух способов 

for(int i = 0; i < 102; i++)
        for(int j = 0; j < 1002; j++)
            t[i][j] = -1;

Это вы уже знаете.

Другой способ - использовать функцию memset. 

memset(t, -1, sizeof(t));
0 голосов
/ 28 мая 2020

Как утверждали другие, вы просто устанавливаете первый элемент в -1. Я предложу альтернативу memset на C ++ 11. Должна быть примерно такая же производительность, если вы используете параметр оптимизации компилятора -O2. 

std::fill_n(&t[0][0], sizeof(t)/sizeof(int),-1);

edit: для опечаток

...