Get najbliższą wartość dla kombinacji tablicy (JS)

Question

szukam algorytmu, który można wykorzystać do łączenia wartości w tablicy, aby uzyskać jak najbardziej zbliżone do „inna wartość”.

Na przykład, liczba chcę, aby dowiedzieć się, jaka kombinacja, która daje zamyka doprowadzić do 2.5. A moja tablica to [0.5, 1.0, 1.5, 2.0, 3.0]. Połączenie w tym przypadku miałoby postać 2.0+0.5.

2.7 dałoby takie samo combo (2,5 jest najbliższe), podczas gdy 3.7 dałoby 3.0+0.5, a 7.0 miałoby być 3.0+3.0+1.0.

Czytałem różne algorytmy, aby utworzyć dostępne kombinacje i takie - na przykład: https://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations Jednak mam trudności z napisaniem funkcji, która pozwala na użycie tej samej wartości wiele razy (np. mój przykład z 7.0). To sprawia, że ​​liczba kombinacji jest dość duża.

Każdy po dobrym przykładem schowany? Czy masz jakieś wskazówki do przekazania?

EDYTOWANIE @kar powiedział mi o "problemie z plecakiem". Mogę dodać, że dla mojego przykładu poszukiwana wartość znajduje się w określonym zakresie (1,0 i 10,0) - co nieco ogranicza kombinacje.

Answer 1

Problemu jest mieszaniną Coin Problem i Knapsack Problem

Jeśli monety są stosowane tylko raz

danego zbioru wartości S, n = | S | wm: wartość w przybliżeniu

DEFINE BEST = { } 
DEFINE SUM = 0 
DEFINE K = 0 

WHILE S IS NOT EMPTY DO 
    K = K + 1 
    FIND MIN { Si : |(SUM+Si) - m| is minimal } 
    ADD TUPLE < Si, |(SUM+Si) - m|, K > to BEST 
    SUM = SUM + Si 
    REMOVE Si from S 
END-FOR 

RETURN BEST 

algorytm ten prowadzi się w czasie: O (| S |) ~ O (n)

Set BEST będzie miał n rozwiązania dla każdego k: 1..n

dla K: trzeba optymalnego wyboru na tym etapie

aby znaleźć kompletne rozwiązania:

GIVEN BEST = { < COIN:X, DISTANCE:Y, DEGREE:K > } 
DEFINE SOLUTION = { } 
Y" = MINIMUM Y IN BESTi.Y for i: 1..n 
KEEP ADDING BESTj.X to SOLUTION UNTILL BESTj.Y = Y" FOR j: 1..n 

Jeśli monety mogą być ponownie użyte:

DEFINE SOLUTION = { } 
DEFINE SUM = 0 
LESS = { Si : Si < m } 
SORT LESS IN DESCENDING ORDER 
FOR Li in LESS DO 
    WHILE (SUM+Li) <= m DO 
     SUM = SUM + Li 
     ADD Li TO SOLUTION 
    END-WHILE 

    IF SUM = m THEN BREAK-FOR 
END-FOR 
RETURN SOLUTION 

W JavaScript:

function coinProblem (var coins, var value) 
{ 
    var solution = new Array(); 
    var sum = 0; 
    var less = new Array(); 

    for (var i in coins) 
     if (i <= value) 
      less.push(i); 

    // sort in descending order 
    less.sort(); 
    less.reverse(); 

    for (var i in less) 
    { 
     while ((sum+i) <= value) 
     { 
      solution.push(i); 
      sum = sum + i; 
     } 

     if (sum == value) break; 
    } 

    return solution; 
} 

Answer 2

Wypróbuj ten prosty algorytm (JSFiddle demo):

/** 
* @param src {Array} List of available values 
* @param val {Number} Target value 
* @returns {Array} 
*/ 
function get_combinations(src, val) 
{ 
    var result = []; 
    var source = src.slice(); 
    source.sort(); 

    while (val > 0) 
    { 
     for (var i = source.length - 1; i >= 0; i--) 
     { 
      if (source[i] <= val || i == 0) 
      { 
       val = val - source[i]; 
       result.push(source[i]); 
       break; 
      } 
     } 
    } 

    return result; 
}