-1

Я не знаю, где я делаю неправильно. Вот мой код для memoized классической проблемы с рюкзаком (проблема с рюкзаком 0-1). Я не получаю правильный вывод. Кажется, я не строю правильную логику.Я не знаю, моя ошибка в мемориальной версии классического рюкзака

//program to print maximum profit in classic knapsack problem 
#include<iostream> 
using namespace std; 
int **K; 
int max(int a,int b)  //utility function to return maximum of 2 no's 
{ 
     return (a>b)?a:b; 
    } 
int knapsack(int *val,int *wt,int n,int W) 
{ 
if(K[n][W]!=-1)  //if knapsack(val,wt,n,W) has been previously called 
    return K[n][W]; 
if(n<=0||W<=0)  //base condition 
{ 
    K[n][W]=0; 
    return 0; 
} 
if(wt[n]<=W)  //if there is place for nth item in knapsack bag 
{ 
    K[n][W]=max(val[n-1]+knapsack(val,wt,n-1,W-wt[n-1]),knapsack(val,wt,n-1,W));   //check whether it is profitable to keep nth item or not 
    return K[n][W]; 
} 
else    //there is no space for nth item in bag 
{ 
    K[n][W]=knapsack(val,wt,n-1,W); 
    return K[n][W]; 
} 
    } 
int main() 
{ 
int n,*val,*wt,W; 
cin>>n; 
val=new int[n]; 
wt=new int[n]; 
for(int i=0;i<n;i++)  
    cin>>wt[i]>>val[i]; 
cin>>W; 
K=new int*[n+1]; 
for(int m=0;m<=n;m++)  //initialize memorized cache 
{ K[m]=new int[W+1]; 
    for(int n=0;n<=W;n++) 
     K[m][n]=-1; 
} 
cout<<knapsack(val,wt,n,W); //solves problem 
} 

Я не хочу это решать с помощью итеративного метода, потому что я хочу практиковать запоминание и динамическое программирование.

+1

Что происходит, когда вы запускаете это? Какую проблему вы испытываете в частности? – halfer

+0

Я думаю, что ошибся в логике –

+0

Удобный и быстрый взгляд, но базовое условие опасно, если n или W на самом деле ниже 0. Не знаю, если C# выдает ошибку или нет, и если ваш вызов с W-wt [n-1] может оказаться ниже 0. Однако его плохое создание ложных базовых условий –

ответ

0

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

ранее я сравниваю W с размером (п + 1) -го элемента

if(wt[n-1]<=W)  //if there is place for nth item in knapsack bag 
{ 
    K[n][W]=max(val[n-1]+knapsack(val,wt,n-1,W-wt[n-1]),knapsack(val,wt,n-1,W));   //check whether it is profitable to keep nth item or not 
    return K[n][W]; 
    } 

и практическое базовое условие для ранцевого задачи

if(n==0||W==0)  //base condition. Also means there is no item remaining to be consider or there is no space remaining for item 
    { 
     K[n][W]=0; 
     return 0; 
    }