Problem in code

#1

Whats the problem in my code that its not working? Also can you specify test cases where its failing?

#2

hello @kunal81198
read this carefully->

image

#3

first remove all those packet whose value is -1
and then apply 0-1 knapsack.
check ->

#4

but i have already made a condition about that -1 in if else part in knapscak function. Also its a problem of unbounded knapsack not 0-1

#5

yeah , 0-n knapsack (that was typo)

#6

check input format . …

#7

So are you saying that i should take input if price is -1?

#8

also doesnt this line take care of -1 thing?
if(price[i-1]>0)
dp[i][j]=min(price[i-1]+dp[i][j-weight[i-1]],dp[i-1][j]);

#9

i m talking about input format.

image

why r u reading n elements? N has no role in this problem.
u are given W prices and their weight is i+1 .(read input format)

#10

int n,total_weight;
cin>>n>>total_weight;
int weight[n];
int price[n];
for(int i=0;i<total_weight;i++)
{
cin>>price[i];
}
for(int i=0;i<total_weight;i++)
{
weight[i]=i+1;
}
cout<<Knapsack(weight,price,total_weight,n);

#11

Is this input correct?

#12

why n here? n shold be replaced with total weight

#13

bro 1 test case still failing pls help

#14
#15

image

add this price consition in this if.(becuase these two are must condition if we want to include current weight, otherwise dp[i][j]=dp[i-1][j])

#16

But bro i am including it in the next line if(price[i-1]>0) in line 21

#17

what if this condtion fails,ur code will not update dp[i][j] right?
ideally in that case dp[i][j] shpuld be dp[i-1][j]

so either add dp[i][j] shpuld be dp[i-1][j] by writing a separate else of that if.

or mention price condition in outer if

1 Like
#18

Yes got it bro thanks