Minimum money needed

#1

import java.util.Scanner;

public class MinimumMoneyNeeded {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int W = sc.nextInt();
int[] wt = new int[n];
for(int i=0;i<n;i++) {
wt[i] = sc.nextInt();
}
int[] val = new int[n];
for(int i=0;i<n;i++) {
val[i] = wt[i];
}

	System.out.println(knapsack(W,wt,val,n));

}

public static int knapsack(int W,int[] wt,int[] val,int n) {
int[][] K = new int[n+1][W+1];
for(int i=0;i<=n;i++) {
for(int w=0;w<=W;w++) {
if(i==0) {
K[i][w] = Integer.MAX_VALUE;
}
else if(w==0) {
K[i][w] = 0;
}
else if(wt[i-1]<=w) {
K[i][w] = Math.min(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w]);
}
else {
K[i][w] = K[i-1][w];
}
}
}

 return K[n][W];

}
}

//sir I have made little changes to 0-1 Knapsack code for the given code but I’m getting wrong answer

#2

@Siddharth_sharma1808,

your input format is wrong.

GIVEN: First line of input contains two space separated integers N and W, the number of friend he has and the amount of Oranges in kilograms which he should buy.

The second line contains W space separated integers in which the i^th^ integer specifies the price of a ‘i’kg apple packet. A value of -1 denotes that the corresponding packet is unavailable.

You have taken input of prices as n instead of W.

Suggested Approach:

  • Create matrix min_cost[n+1][W+1], where n is number of distinct weighted packets of orange and W is maximum capacity of bag.
  • Initialize 0th row with INF (infinity) and 0th Column with 0.
  • Now fill the matrix
    • if wt[i-1] > j then min_cost[i][j] = min_cost[i-1][j] ;
    • if wt[i-1] <= j then min_cost[i][j] = min(min_cost[i-1][j], val[i-1] + min_cost[i][j-wt[i-1]]);
  • If min_cost[n][W]==INF then output will be -1 because this means that we cant not make make weight W by using these weights else output will be min_cost[n][W].
#3

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.