Here I have two functions for the recursive knapsack problem while knapsack() gives the correct output (i.e 220) but knapsack1() gives wrong value (i.e 60) .Can anyone please explain why?
#include<iostream>
#include<stdio.h>
using namespace std;
long knapsack1(long w,long wt[],long val[],long n)
{
if(n==0||w==0)
{
return 0;
}
if (wt[n] > w)
{
n--;
}
else
{
return max(knapsack1(w,wt,val,n-1),val[n]+knapsack1(w-wt[n],wt,val,n-1));
}
}
long knapsack(long w,long wt[],long val[],long n)
{
if(n==0||w==0)
{
return 0;
}
if (wt[n] > w)
{
return knapsack(w, wt, val, n-1);
}
else
{
return max(knapsack(w,wt,val,n-1),val[n]+knapsack(w-wt[n],wt,val,n-1));
}
}
int main()
{
long val[] = {60, 100, 120};
long wt[] = {10, 20, 30};
long w = 50;
long n = sizeof(val)/sizeof(val[0]);
printf("%d", knapsack(w, wt, val, n));
printf("%d", knapsack1(w, wt, val, n));
return 0;
}
Aucun commentaire:
Enregistrer un commentaire