Ottenere il valore più vicino per le combinazioni di un array (JS)

Question

Sto cercando un algoritmo che possa essere utilizzato per combinare i valori nell'array, per avvicinarsi il più possibile a "un altro valore".

Ad esempio, il numero che voglio scoprire è la combinazione che dà il risultato della chiusura a 2.5. E il mio array è [0.5, 1.0, 1.5, 2.0, 3.0]. La combinazione in questo caso sarebbe 2.0+0.5.

2.7 fornirebbe la stessa combinazione (2,5 è il più vicino), mentre 3,7 restituirebbe 3.0+0.5 e 7.0 sarebbe 3.0+3.0+1.0.

Ho letto su diversi algoritmi per creare combinazioni disponibili e simili, ad esempio questo: https://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations Tuttavia, ho difficoltà a scrivere una funzione che consente di utilizzare lo stesso valore più volte (come il mio esempio con 7.0). Questo rende il numero di combinazioni abbastanza grande.

Chi ha un buon esempio nascosto? O hai qualche indicazione da dare?

EDIT @zkar mi ha parlato del "problema dello zaino". Posso aggiungere che per il mio esempio, il valore ricercato si trova in un intervallo specificato (1.0 e 10.0), il che limita un po 'le combinazioni.

Answer 1

Il tuo problema è un misto di Coin Problem e Knapsack Problem

Se monete sono usati solo una volta:

Dato un insieme di valori S, n = | S |, m: valore per approssimare

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 

Questo algoritmo viene eseguito in tempo: O (| S |) ~ O (n)

Il set Migliore avrà n soluzioni, per ogni K: 1..n

per K: si ha la scelta ottimale in quella fase

per trovare la soluzione completa:

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 

Se le monete possono essere riutilizzati:

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 

In 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

si può provare questo semplice algoritmo (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; 
}