java - 从一组包含项目的数组中获取最佳组合

Question

我有一组元素数组，如下所示:

1. A [8] = [1 1 1 1 1 1 1 1 ] 米
2. B [5] = [5 5 5 5 5 ] 米
3. C [7] = [0.5 0.5 0.5 0.5 0.5 0.5 0.5 ] 米

我想从上面的容器中获得最佳的元素组合。

比如得到7米的尺寸

• 选项 1:我们可以从 A 中取出 7 项(1+1+1+1+1+1+1)
• 选项 2:我们可以从 B 取 1 个项目，从 A 我们可以取 2 个 (5 + (1 + 1))
• 选项 3:我们可以从 B 取 1 项，从 C 取 4 (5 + (.5*4))
• 选项 4:我们可以从 B 取 1 个项目，从 B 取 1 个，从 C 我们可以取 2 个 (5 + 1 + (.5*2))

让我知道如何解决这个问题。我试过背包，但很难找到最好的组合。

提前致谢

Answer 1

我已经为您编写了这个简单的方法，包括 Resource用于提供的示例的类。

private static class Resource {
      private double value;
      private int available;

          public Resource(double value, int available) {
             this.value = value;
             this.available = available;
          }

          public void setValue(double value) {
             this.value = value;
          }

          public double getValue() {
             return this.value;
          }

          public void setAvailable(int available) {
             this.available = available;
          }

          public int getAvailable() {
             return this.available;
          }
       }

在屏幕上打印数字的方法

public static void findNumbers(Resource[] availableResources, double targetNumber) {
      // Keeps Track of which resource is currently in use.
      int resourceInCheck = 0;
      // Remainder of the wanted number
      double remainder = targetNumber;

      System.out.print("Values: ");
      while(remainder > 0) {
         if(remainder >= availableResources[resourceInCheck].getValue() && availableResources[resourceInCheck].getAvailable() > 0) {

            System.out.print(availableResources[resourceInCheck].getValue() + ", ");

            remainder -= availableResources[resourceInCheck].getValue();

            availableResources[resourceInCheck].setAvailable( (availableResources[resourceInCheck].getAvailable() - 1) );
         }
         else {
            resourceInCheck++;
         }
      }
   }

主要方法

public static void main(String[] args){

      Resource firstResource = new Resource(5, 5);
      Resource secondResource = new Resource(1, 8);
      Resource thirdResource = new Resource(0.5, 7);

      Resource[] availableResources = {firstResource, secondResource, thirdResource};

      findNumbers(availableResources, 17.5);
   }

输出

Values: 5.0, 5.0, 5.0, 1.0, 1.0, 0.5,

同样，这是一个适合这个问题特点的可能解决方案，显然还有其他方法可以解决它。

注意: targetNumber应该是 <=比所有可用资源的总和。

注意2:资源数组需要按值从大到小排序。