java - 如何找到有效子集和最佳有效子集？

Question

我正在尝试解决二维 0-1 全背包问题，使用强力方法生成所有可能的子集并选择最有值(value)的子集。然而，我未能成功找到有效的子集，以及从这些有效子集中的最佳选择。

我创建了一个 Item 类，其中包含值、大小和重量变量以及 getter 和 setter。

我还弄清楚了如何生成所有子集。

子集的总重量和尺寸必须等于背包的重量和尺寸，否则包装将无法进行。

但是对于我的一生，我不知道如何选择获胜的子集。 我知道，首先，必须找到所有有效的子集(总尺寸和重量等于背包的尺寸和重量)，然后在这些子集中最有值(value)的就是所选择的包装。

要查看子集是否有效，我假设必须有一个 if 语句，例如

if (subsetSize == knapsackSize && subsetWeight == knapsackWeight)
      subset is valid

但我无法找出最好的方法来做到这一点。

我也无法弄清楚是否应该将子集值存储到列表中的某个位置来比较它们，或者是否有我没有看到的更好的方法。

例如，这是我查找子集的值、大小和重量的失败之一。

for(int i = 0; i <setOfSubsets.size(); i ++) {
                for (int j = 0; j < setOfSubsets.get(i).size(); j ++) {



                    subsetSizeList.add(setOfSubsets.get(i).get(j).getSize());
                    subsetWeightList.add(setOfSubsets.get(i).get(j).getWeight());
                    subsetValueList.add(setOfSubsets.get(i).get(j).getValue());

这是其余代码的样子。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class FullKnapsack2D {


    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        ArrayList<Item> itemList = new ArrayList<Item>();
        List<ArrayList<Item>> setOfSubsets = new ArrayList<ArrayList<Item>>();

        System.out.println("Enter the knapsack weight and size capacity (separate by space): ");
        int knapsackWeight = s.nextInt();
        int knapsackSize = s.nextInt();

        System.out.println("How many items?");
        int numberOfItems = s.nextInt();

        for (int i = 0; i < numberOfItems; i ++) {
            System.out.println("Enter the value, size, and weight for item " + (i + 1));
            Item newItem = new Item(s.nextInt(), s.nextInt(), s.nextInt());
            itemList.add(newItem);
        }

        System.out.println("Running...");

        long startTime = System.currentTimeMillis();

        for(int i = 0; i < itemList.size(); i ++) {

            List<ArrayList<Item>> setCopy = new ArrayList<ArrayList<Item>>();

            // Make a setCopy of all existing subsets
            for(ArrayList<Item> subset : setOfSubsets) {
                setCopy.add(new ArrayList<Item>(subset));
            }

            //Add the new element to each of the existing subsets
            for(ArrayList<Item> subset : setCopy) {
                subset.add(itemList.get(i));
            }

            //Add the new element as a standalone set
            ArrayList<Item> standalone = new ArrayList<Item>();
            standalone.add(itemList.get(i));
            setCopy.add(standalone);

            setOfSubsets.addAll(setCopy);
        }

            //Print out all subsets
            for(ArrayList<Item> subset : setOfSubsets) {
                System.out.println(subset);
            }


        //if the sum total of a subset's value is higher than every other subset's value &&
        // the sum total of a subset's weight and size is equal to the knapsack's
        // weight and size, then 

        //System.out.println("Found an optimal packing:");

        //for(Item item : subset){
        // System.out.println(item.toString());
        //}
            ```

Answer 1

似乎是一个简单的逻辑问题。由于您已经获得了所有可能的组合，因此您需要做的是:

对于每个子集，

1. 计算所有元素的总尺寸、重量和值(value)。
2. 如果总尺寸等于背包尺寸，总重量等于背包重量，检查总和是否是迄今为止最大的
3. 如果是，请将其存储为迄今为止最好的子集

ArrayList<Item> bestSubset = null;
int bestValue = 0;
for(ArrayList<Item> subset : setOfSubsets){
    int totalSize = 0;
    int totalWeight = 0;
    int totalValue = 0;
    for(Item i : subset){
        totalSize += i.getSize();
        totalWeight += i.getWeight();
        totalValue += i.getValue();
    }
    if(totalSize == knapsackSize && totalWeight == knapsackWeight && totalValue > bestValue){
        bestSubset = subset;
        bestValue = totalValue;
    }
}