Help with error

#1

code: https://ide.codingblocks.com/s/426969

problem: https://hack.codingblocks.com/app/contests/2022/146/problem

not getting the correct ouput

#2

Make all indexes of your amount array as 0, they are carrying garbage value in them
Pass value of n to, as your weight variable is acting as pointer, so it won’t be equal to size of array
Also check if weight[i]<=j instead of it’s reverse
Do this and let me know if it works or not cause everything except these seems right.

#3


i’m gettng an answer but it’s the wrong one

#4

Check now ->

#5

I found this problem very similar to the coin change problem where there is an infinite amount coins to make the change( https://hack.codingblocks.com/app/contests/2022/591/problem)

What I don’t understand is that in the coin problem the loops are opposite of the 0-N knapsack.
Here we are iterating over for one coin over all the denominations but in the knapsack one we are iterating over all the items for one particular amount first

for(int j = 0; j < n  ; j++){ // make change for all denom one coin at a time
            for(int i = 1 ; i  <= amt ; i++){ 
			if(denom[j]  <= i){ // if we can make change for the current amount with the current denom
				ways[i] += ways[i - denom[j]];  
                ways[i] = ways[i]%1000000007;
			}

// 0-knapsack
    		for(int i = 0; i <= capacity; i++){
		for(int j = 0; j < n; j++){
			if(weights[j] <= i)
			amount[i] = max(amount[i], amount[i - weights[j]] + value[j]);
		}



`
#6

Watch this coin change problem from here, explained in great detail. No doubts will be left after you watch this.

#7

no no I already solved it but I can’t understand what is the difference between these two problems because they look very similar but their approaches are a bit different mainly the loops that I mentioned

#8

Oh okay I will watch the video

#9

Solution for them is little bit same, but are different too. If you will have issue to understand 0-n knapsack too, let me know. Will suggest you good resource to understand it too.

#10

Yeah please share maybe I will understand better

#11

Problem statement is not same, but will do the work

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.