0

我正在尝试解决二维 0-1 全背包问题，使用一种蛮力方法生成所有可能的子集并选择具有最大价值的子集。但是，我未能找到有效的子集，以及从这些有效子集中的最佳选择。

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

我还想出了如何生成所有子集。

子集的总重量和尺寸必须等于背包的重量和尺寸，否则包装将不起作用。

但是对于我的生活，我无法弄清楚如何选择获胜的子集。我知道首先，必须找到所有有效的子集（总尺寸和重量等于背包的尺寸和重量），然后在这些子集中具有最大价值的是选择的包装。

要查看子集是否有效，我假设必须有一个 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());
        //}
            ```
4

1 回答 1

1

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

对于每个子集，

  1. 计算所有物品的总尺寸、重量和价值。
  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;
    }
}
于 2020-03-07T01:34:23.927 回答