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

Question

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

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(，最大重量=5；如果第1项和第4项的值相同，则应选择权重较小的第4项。如何在上面的代码中实现这个条件。问题说明：

您的目标是确定要将哪些内容放入包装，使总重量小于或等于包装并且总成本尽可能大。你更愿意寄一个重量较小的包裹，以防有多个相同价格的包装。

Answer 1

如果您想通过最小化重量来最大化值。你可以查看

设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的问题，这就是为什么我没有解释第一个和第二个条件！！

Answer 2

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

Answer 3

您可以使用Branch and Bound Algorithm。

样本代码-

考虑到物品是你的POJO与重量和价格。介绍一种方法byRatio()如下-

 public static Comparator<Item> byRatio() {
        return (i1, i2) -> Double.compare(i2.calculateRatio(), i1.calculateRatio());
    }
public double calculateRatio() {
        return price / weight;
    }

这将有助于按比例对项目列表进行排序。

让我们现在编写核心逻辑-

 public List<Item> buildOptimalPackageWithBBAlgo(List<Item> items, double maxWeight) {
        items.sort(Item.byRatio());
        Node optimal = fetchOptimalNode(items, maxWeight);
        return optimal.items;
    }
 /**
     * This method used Branch and bound algorithm to search for the
     * optimal node.
     *
     * @param  items  sorted items by ratio of price to weight
     * @param  maxWeight maximum weight the package is allowed to hold
     * @return optimal node
     */
private Node fetchOptimalNode(List<Item> items, double maxWeight) {
    Node optimal = new Node();
    Node root = new Node();
    root.calculateBound(items, maxWeight);
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        if (node.bound > optimal.price && node.height < items.size() - 1) {
            Node edgeNode = new Node(node);
            Item item = items.get(node.height);
            edgeNode.weight += item.getWeight();
            if (edgeNode.weight <= maxWeight) {
                edgeNode.items.add(items.get(node.height));
                edgeNode.price += item.getPrice();
                edgeNode.calculateBound(items, maxWeight);
                if (edgeNode.price > optimal.price) {
                    optimal = edgeNode;
                }
                if (edgeNode.bound > optimal.price) {
                    queue.offer(edgeNode);
                }
            }
            Node leafNode = new Node(node);
            leafNode.calculateBound(items, maxWeight);
            if (leafNode.bound > optimal.price) {
                queue.offer(leafNode);
            }
        }
    }
    return optimal;
}
private class Node implements Comparable<Node> {
    public int height;
    List<Item> items;
    public double bound;
    public double price;
    public double weight;
    public Node() {
        items = new ArrayList<>();
    }
    public Node(Node parent) {
        height = parent.height + 1;
        items = new ArrayList<>(parent.items);
        bound = parent.bound;
        price = parent.price;
        weight = parent.weight;
    }
    public int compareTo(Node other) {
        return (int) (other.bound - bound);
    }
    private void calculateBound(List<Item> items, double maxWeight) {
        int i = height;
        double w = weight;
        bound = price;
        Item item;
        do {
            item = items.get(i);
            if (w + item.getWeight() > maxWeight) break;
            w += item.getWeight();
            bound += item.getPrice();
            i++;
        } while (i < items.size());
        bound += (maxWeight - w) * (item.getPrice() / item.getWeight());
    }
}

限制-此逻辑仅适用于大于2的项。对于少于2个项目，就时间复杂性而言，这超出了工程设计。

只需使用贪婪算法即可。