Summe aus Kombinationen /permutationen einer Liste mit einer Obergrenze

[strußi]

Hallo Leute,

ich steh gerade extrem auf dem Schlauch.
Aufgabe: Man hat x Kassenzettel. Summiere diese so auf, dass eine Obergrenze mit möglichst kleinem Überschuss erreicht wird.

Ich häge da gerade voll in der Luft. Ich erinnere mich soetwas schon mal gemacht zu haben, finde das Programm aber nicht mehr.

Spoiler: code

import java.util.ArrayList;
import java.util.List;

public class BestWay{

    /**
     * @param args the command line arguments
     */
    public static void main( String[] args ){
        double sum =0; 
        double max =200d; //obergrenze
        //werte
        List<Double> values =new ArrayList<>();
        values.add( 46.38); values.add( 30.99); values.add( 11.10); values.add( 49.75);
        values.add( 29.79); values.add( 29.81 ); values.add( 42.47); values.add( 4.92);       
       
        for (int i=0; i < values.size(); i++){
           sum += values.get(i);
            for (int b=0; b < values.size(); b++){
                sum= sum + values.get(b);
                System.out.println(sum);
            }
        }
    }
   
}

Vielen Dank für eure Hilfe

 

[stg]

Summiere diese so auf, dass eine Obergrenze mit möglichst kleinem Überschuss erreicht wird.

Was soll das denn bedeuten? Ist das der vollständige Wortlaut der Aufgabenstellung?

 

[strußi]

Es geht darum einen bestimmten Wert zu erreichen (hier 200). Ist es nicht möglich 200 exakt zu erreichen soll der Wert (>200) mögliches nahe bei 200 liegen.

 

[strußi]

Meines Verständnisses nach: alle Permutationen erstellen und jedes neue Tupel addieren und schauen welches am nächsten dran ist

 

[Flown]

Woran hakt es jetzt?

 

[strußi]

an der permutation^^

 

[Flown]

Wie würdest du das denn auf dem Papier lösen?

 

[strußi]

erst einmal alle zahlen nebenander schreiben (liste, array wie auch immer) und anschließend die erste zahl behalten und die zweite durchschieben, ...
so erhalte ich einen haufen neuer Listen bei denen ich solange addiere bis ich >= 200 komme

 

[Flown]

Hier mal eine Hilfestellung (in Scala):

def nearestSum(limit : Double, numbers : Array[Double]) : Double = {
  def nearestSum(sum : Double, index : Int) : Double = {
    if(numbers.length == index || sum == limit) {
      sum
    } else {
      val x = nearestSum(sum + numbers(index), index + 1)
      val y = nearestSum(sum, index + 1)
      if(Math.abs(limit - x) < Math.abs(limit - y)) x else y
    }
  }
  nearestSum(0d, 0)
}

 

[strußi]

Oh boy, ich habe noch nie Scala programmiert. Im groben steig ich durch, werde mich morgen noch mal melden
Danke

 

[Flown]

Es ging eigentlich um die Idee, nicht um Scala speziell.