Select items in 0/1 knapsack ,where two items have same benefits |maximize value and minimize weight

Question

In 0/1 knapsack problem, how do I select items, if two items have same value. The value with the lesser weight should be selected , how do I check that condition? I have the following function using Dynamic programming.

static int[] knapsack(int maxWeight, double[] weight, double[] value, int n) {
    //n = no. if items
    int i, w;

    double array[][] = new double[n + 1][maxWeight + 1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= maxWeight; w++) {
            if (i == 0 || w == 0)
                array[i][w] = 0;
            else if (weight[i - 1] <= w)
                array[i][w] = max(value[i - 1] + array[i - 1][(w -(int) weight[i - 1])], array[i - 1][w]);
            else
                array[i][w] = array[i - 1][w];
            if (i != 0 || w != 0)
                System.out.print(array[i][w] + "\t");
        }
        System.out.println();
    }

    int[] selected = new int[n + 1];
    for (int j = n, wt = maxWeight; j > 0; j--) {   
        if (array[j][wt] != array[j - 1][wt]) {
            if (array[j][wt] == array[j][wt - 1]) {
                selected[j] = 0;
                break;
            }
            selected[j] = 1;
            wt = wt - (int) weight[j - 1];
        }
        else
            selected[j] = 0;
    }
    /** Print finally selected items **/
    System.out.println("\nItems selected : ");
    for (int k = 1; k < n + 1; k++)
        if (selected[k] == 1)
            System.out.print(k +" ");
        System.out.println();

        return selected;
}

For this type of case : (i,v): (4,45)(3,20)(5,30)(2,45) ,maxWeight = 5; where item 1 and 4 have same value, it should select the item with lesser weight that is 4th. how do I implement this condition in above code. Problem statement :

Your goal is to determine which things to put into the package so that the total weight is less than or equal to the package limit and the total cost is as large as possible. You would prefer to send a package which weights less in case there is more than one package with the same price.

Answer 1

If you mean to maximise value with minimising Weight . You can check that

Let DP[i][j] be the maximal value that can be obtained!

And W[i][j] the minimal weight that is to be used!!

Then,

if(Current Weight > Element's Weight)
{
      if(DP[i-1][j-Weight[i]]+Value[i]>DP[i-1][j]){
             DP[i][j]=DP[i-1][j-Weight[i]]+Value[i];
             Weight[i][j]= Weight[i-1][j-Weight[i]]+Value[i]
      }
      else if(DP[i-1][j-Weight[i]]+Value[i] <  DP[i-1][j] ){
             DP[i][j]=DP[i-1][j];
             Weight[i][j]=Weight[i-1][j];
      } 
      else{                   //Note this is the tricky part elsewise the 
                              //Above conditions are simple Knapsack conditions

             DP[i][j]=DP[i-1][j];   //Both of them are equal We will get same Value . Thus we cannot maximise it in any other way!!
             Weight[i][j]=minimum ( Weight[i-1][j] ,Weight[i-1][j-Weight[i]]+A[i]);

      }
}
else
{
             DP[i][j]=DP[i-1][j];
             Weight[i][j]=Weight[i-1][j];
}

Note the solution is trivial unless the third condition in first if! We need to maximise the fun at any cost! So we aren't Messing with it ! But when the fun from both cases is same , We need to pick the one with lesser weight elsewise We will end up having more weight for same value of knapsack!

I have assumed you know knapsack 0/1 problem that is why I haven't explained first and second conditions !!