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

Question

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

您想向您的 friend 发送一个装有不同元素的包裹。您放入包裹中的每一件元素都有索引号、重量和成本等参数。

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

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

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

输出:为每组事物生成一个你放入包中的事物列表(它们的索引号用逗号分隔)。如果所有元素都不适合包裹，打印一个连字符 (-).

测试 1输入 81 : (1,53.38,$45) (2,88.62,$98) (3,78.48,$3) (4,72.30,$76) (5,30.18,$9) (6,46.34,$48)

预期输出 4

测试 2

Test Input 75 : (1,85.31,$29) (2,14.55,$74) (3,3.98,$16) (4,26.24,$55) (5,63.69,$52) (6,76.25,$75) (7,60.02,$74) (8,93.18,$35) (9,89.95,$78)

预期输出 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();
    }
}