字符串输入的背包解决方案

Question

我进行了在线编码测试，问题描述如下。我无法完成这个问题，但确实就如何提出一个潜在的解决方案发表了一些评论。我想知道什么是解决这个问题的最佳方法。我遇到的主要问题是将给定的输入拆分为字符串并找到合适的集合来放入它们。下面是问题。

您想给您的朋友寄一个装有不同物品的包裹。您放入包裹中的每一件物品都有索引号、重量和成本等参数。

包裹有重量限制。您的目标是确定将哪些东西放入包裹中，以便总重量小于或等于包裹限制并且总成本尽可能大。

如果有多个相同价格的包裹，您更愿意寄重量较轻的包裹。这是背包问题的变体。

输入：您的程序应该从标准输入中读取行。每行包含一个包裹可以承受的重量（在冒号之前）和您需要挑选的物品清单。每件物品都用括号括起来，其中第一个数字是物品的索引号，第二个是它的重量，第三个是它的成本。任何包裹可以携带的最大重量是 <= 100. 您最多可能需要从 15 项中进行选择。任何东西的最大重量和最大成本是 <= 100.

输出：为每组事物生成一个你放入包中的事物列表（它们的索引号用逗号分隔）。如果 none 件物品适合包装，打印连字符 (-).

测试 1 输入81 : (1,53.38,) (2,88.62,) (3,78.48,) (4,72.30,) (5,30.18,) (6,46.34,)

预期输出4

测试 2

Test Input 75 : (1,85.31,) (2,14.55,) (3,3.98,) (4,26.24,) (5,63.69,) (6,76.25,) (7,60.02,) (8,93.18,) (9,89.95,)

预期输出2,7

Answer 1

您最多可能需要从 15 项中进行选择。所以你有可能的组合 2^15 = 32,768。这样你就可以检查每个组合，找出符合要求的组合。

示例：有 3 (1,2,3) 个事物。然后你可以选择：（），（1），（2），（3），（1,2），（1,3），（2,3），（1,2,3）。现在需要找到符合要求的组合。

解决方法如下：

 public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String s = in.nextLine();
    String res[] = s.replaceAll("[^0-9.]+",";").split(";");
    double target = Integer.parseInt(res[0]);
    int n = (res.length-1) / 3;
    int[] Index = new int[20];
    double[] P = new double[20];
    double[] W = new double[20];
    int jj = 0;
    for(int i = 1; i < res.length; i +=3){
        Index[jj] = Integer.parseInt(res[i]);
        W[jj] = Double.parseDouble(res[i+1]);
        P[jj++] = Double.parseDouble(res[i+2]);
    }
    double result = 0;
    int track = 0;
    double resSum = 0;
    for(int i =0; i< (1<<n); i++){
        double sum = 0;
        double weight = 0;
        for(int j=0; j < n; j++){
            if(((1<<j)&i) > 0){
                sum+= P[j];
                weight+=W[j];
            }
        }
        if(weight <= target){
            if(sum > resSum){
                result = weight;
                track = i;
                resSum = sum;
            }else if(sum == resSum && weight < result){
                result = weight;
                track = i;
            }
        }
    }
    jj = 0;
    for(int i = 0; i < n; i++){
        if(((1<<i)&track) > 0){
           if(jj > 0){
               System.out.print(",");
           }
           jj = 1;
           System.out.print(Index[i]);
        }
    }
    if(track == 0){
        System.out.println("-");
    }else {
        System.out.println();
    }
}

字符串输入的背包解决方案

Knapsack solution for input of strings

java

collections

knapsack-problem