Select 个物品在 0/1 个背包中，其中两个物品具有相同的好处 |最大化价值并最小化重量

Question

在 0/1 背包问题中，如果两个项目具有相同的值，我如何 select 项目。权重较小的值应该是 selected ，我如何检查该条件？我有以下使用动态编程的功能。

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;
}

对于这种情况：(i,v): (4,45)(3,20)(5,30)(2,45) ,maxWeight = 5; 如果第 1 项和第 4 项具有相同的值，则应该 select 重量较小的第 4 项。我如何在上面的代码中实现这个条件。问题陈述：

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

如果您只需要 select 权重最低的项目，那么为什么不让它循环遍历选项并将 object[i] 的权重与某个对象的权重进行比较[i + 1] 如果较低则与下一个比较，否则 object[i] = object[i + 1]，依此类推。我是否正确理解了这个问题？

Answer 2

如果你的意思是最大化值并最小化权重。你可以检查

设DP[i][j]为可取的最大值！

W[i][j]是要使用的最小权重！！

然后，

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];
}

注意解决方案很简单，除非第一个 if 中的第三个条件！我们需要不惜一切代价最大化乐趣！所以我们不是在搞乱它！但是当两种情况的乐趣相同时，我们需要选择重量更轻的那个否则我们最终会以相同的背包价值获得更多的重量！

我假设你知道背包 0/1 问题，这就是为什么我没有解释第一个和第二个条件！！

Select 个物品在 0/1 个背包中，其中两个物品具有相同的好处 |最大化价值并最小化重量

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

java

knapsack-problem

dynamic-programming