アイテム

Question

Iが蛇腹のような要素のアレイのセットを有するを含む配列のセットから最適な組み合わせを得る：

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]メートル

Iは、容器の上方から商品の最良の組合せを取得したいです。例えば

は7メートルのサイズを取得する

• オプション1：我々は7アイテムを取ることができるAからの（1 + 1 + 1 + 1 + 1 + 1 + 1）
• オプション2：からB私たちは1つのアイテムを取ることができ、Aから2つ（5 +（1 + 1））
• オプション3：Bから私たちは1アイテムを取ることができ、Cからは4（5 + ）
• オプション4：Bテイク1から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：リソースの配列は、大きい値から小さい値にソートする必要があります。

Answer 2

おそらく、すべての可能な組み合わせを生成し、希望する合計と比較して&を計算するのは、最も簡単で最も明白でしょう。このような

何か：

:For A :In 0 1 2 3 4 5 6 7 8 
    :For B :In 0 1 2 3 4 5 
     :For C :In 0 1 2 3 4 5 6 7 
      :If (7 == (A * 1) + (B * 5) + (C * 0.5)) 
       [append to list of results] 
      :End 
     :End 
    :End 
:End 

その後、あなたは、これらの結果は、（合計= 7メートル）から選ぶことを得る：17の場合

┌───┬───┬─────┐ 
│1 m│5 m│0.5 m│ 
├───┼───┼─────┤ 
│0 │1 │4 │ 
├───┼───┼─────┤ 
│1 │1 │2 │ 
├───┼───┼─────┤ 
│2 │1 │0 │ 
├───┼───┼─────┤ 
│4 │0 │6 │ 
├───┼───┼─────┤ 
│5 │0 │4 │ 
├───┼───┼─────┤ 
│6 │0 │2 │ 
├───┼───┼─────┤ 
│7 │0 │0 │ 
└───┴───┴─────┘ 

。5メートルの場合：

┌───┬───┬─────┐ 
│1 m│5 m│0.5 m│ 
├───┼───┼─────┤ 
│0 │3 │5 │ 
├───┼───┼─────┤ 
│1 │3 │3 │ 
├───┼───┼─────┤ 
│2 │3 │1 │ 
├───┼───┼─────┤ 
│4 │2 │7 │ 
├───┼───┼─────┤ 
│5 │2 │5 │ 
├───┼───┼─────┤ 
│6 │2 │3 │ 
├───┼───┼─────┤ 
│7 │2 │1 │ 
└───┴───┴─────┘ 

し、道に沿って、あなたはすべての可能な独特の合計の長さ（そこには大きな驚き:-)）を解決することができます

┌─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┐ 
│0│0.5│1│1.5│2│2.5│3│3.5│4│4.5│5│5.5│6│6.5│7│7.5│8│8.5│9│9.5│10│10.5│11│11.5│12│12.5│13│13.5│14│14.5│15│15.5│16│16.5│17│17.5│18│18.5│19│19.5│20│20.5│21│21.5│22│22.5│23│23.5│24│24.5│25│25.5│26│26.5│27│27.5│28│28.5│29│29.5│30│30.5│31│31.5│32│32.5│33│33.5│34│34.5│35│35.5│36│36.5│ 
└─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┘