Minimum money needed: 1 test case failing

#1

import java.util.*;

public class Main{

public static void main(String [] args)
{
	Scanner s = new Scanner(System.in);

	int n = s.nextInt();
	int w = s.nextInt();

	int [] prices = new int [w + 1];
	for(int i = 1; i<=w; i++)
		prices[i] = s.nextInt();

	System.out.println(minMoney(n,w,prices));
}

public static long minMoney(int n, int w, int [] prices)
{
	long [][] strg = new long [w+2][w+1];

	//row represent the array
	//column represents the weight (W)

	for(int i = w+1; i>0; i--)
	{
		for(int j = 0; j<=w; j++)
		{
			//no weight needed
			//then, no price needed
			if(j == 0)
				strg[i][j] = 0;
			
			//if no packet left
			//and we want Wkg of oranges
			//then infinity price is needed
			else if(i == w+1)
				strg[i][j] = Integer.MAX_VALUE;
			
			else
			{
				//if we don't take the packet
				long fp = strg[i+1][j];

				//if we take the current packet
				long sp = Integer.MAX_VALUE;
				if(prices[i] != -1 && i <= j)
					sp = strg[i+1][j-i] + prices[i];

				strg[i][j] = Math.min(fp,sp);
			}
		}
	}

	if(strg[1][w] == Integer.MAX_VALUE)
		return -1;
	else
		return strg[1][w];
}

}

#2

@arjunsabu99,
Input:
5 10
-1 33 -1 176 -1 46 -1 120 -1 300
Correct output:
112
your output:
153

#3

sir i didn’t read that there were infinite no. of orange packets available. Thus, it must be similar to 0/N knapsack and now it is working. I thought one packet is available one time , ie 0/1 Knapsack

1 Like