Erhalten beste Kombination aus einem Satz von Array enthält Elemente

Question

I wie unten eine Reihe von Array von Elementen haben:

1. A [8] = [1 1 1 1 1 1 1 1] meter
2. B [5] = [5 5 5 5 5] Meter
3. C [7] = [0,5 0,5 0,5 0,5 0,5 0,5 0,5] Meter

ich beste Kombination von Gegenständen von oben Behältern erhalten mag.

Zum Beispiel 7 Meter Größe

• Option 1 zu erhalten: von A uns 7 Artikel nehmen können (1 + 1 + 1 + 1 + 1 + 1 + 1)
• Option 2: von B Wir können 1 Stück nehmen und von A können wir 2 nehmen (5 + (1 + 1))
• Option 3: von B können wir 1 Stück nehmen und von C können wir 4 nehmen (5 + (.5 * 4))
• Option 4: B von 1 Einheit wir annehmen, von B 1 nehmen und von C 2 können wir nehmen (5 + 1 + (.5 * 2))

Lassen Sie mich wissen, wie ich das lösen kann. Ich habe versucht mit Rucksack, aber kämpfen, um die beste Kombination zu bekommen.

Vielen Dank im Voraus

Answer 1

Ich habe diese einfache Methode für Sie geschrieben, einschließlich der Resource-Klasse, die für das vorgesehene Beispiel verwendet worden ist.

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; 
      } 
     } 

Methode, die die Zahlen auf dem Bildschirm druckt

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++; 
     } 
     } 
    } 

Haupt Methode

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); 
    } 

Ausgabe

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

Auch dies ist eine mögliche Lösung die Eigenschaften passen dieses Problem, und natürlich gibt es andere Wege, um es anzugehen.

Hinweis:targetNumber sollte <= als die Summe aller verfügbaren Ressourcen sein.

Hinweis2: Array von Ressourcen muss von größeren zu kleineren Werten sortiert werden.

Answer 2

Vielleicht wäre es am einfachsten und am deutlichsten, nur alle möglichen Kombinationen zu generieren und & mit der gewünschten Summe zu vergleichen?

Etwas wie folgt aus:

: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 

Dann erhalten Sie diese Ergebnisse aus (gesamt = 7 m) zur Auswahl:

┌───┬───┬─────┐ 
│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 │ 
└───┴───┴─────┘ 

Für die 17.5-Meter-Fall:

┌───┬───┬─────┐ 
│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 │ 
└───┴───┴─────┘ 

Und auf dem Weg, können Sie alle möglichen eindeutigen Gesamtlängen lösen (keine grossen Überraschungen gibt :-)):

┌─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬─┬───┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┬──┬────┐ 
│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│ 
└─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴─┴───┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┴──┴────┘