किसी सरणी (जेएस)

Question

के संयोजन के लिए निकटतम मूल्य प्राप्त करें मैं एक एल्गोरिदम खोज रहा हूं जिसे मैं "अन्य मान" के रूप में जितना संभव हो सके, सरणी में मानों को संयोजित करने के लिए उपयोग कर सकता हूं।

उदाहरण के लिए, मैं यह जानना चाहता हूं कि बंद करने का परिणाम क्या संयोजन है जो 2.5 है। और मेरी सरणी [0.5, 1.0, 1.5, 2.0, 3.0] है। इस मामले में संयोजन 2.0+0.5 होगा।

2.7 एक ही कॉम्बो (2.5 निकटतम) उत्पन्न करेगा, जबकि 3.7 3.0+0.5 और 7.0 3.0+3.0+1.0 होगा।

मैं उपलब्ध संयोजन बनाने के लिए विभिन्न एल्गोरिदम पर पढ़ रहा हूं और उदाहरण के लिए - उदाहरण के लिए, यह एक: https://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations हालांकि, मुझे एक ऐसा फ़ंक्शन लिखने में कठिनाई हो रही है जो एक ही मान को कई बार उपयोग करने की अनुमति देता है (जैसे 7.0 के साथ मेरा उदाहरण)। इससे संयोजनों की संख्या काफी बड़ी हो जाती है।

कोई भी व्यक्ति जो अच्छा उदाहरण ले रहा है उसे दूर कर दिया गया है? या देने के लिए कोई संकेतक है?

EDIT @zkar ने मुझे "knapsack समस्या" के बारे में बताया। मैं इसे अपने उदाहरण के लिए जोड़ सकता हूं, मांग किए गए मान एक निर्दिष्ट सीमा (1.0 और 10.0) में हैं - जो कुछ हद तक संयोजन को सीमित करता है।

Answer 1

आपकी समस्या Coin Problem का एक मिश्रण और Knapsack Problem

है सिक्के केवल एक बार उपयोग किया जाता है:

मूल्यों एस का एक सेट को देखते हुए, एन = | एस |, मी: मूल्य

अनुमान लगाने के लिए

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 

इस एल्गोरिथ्म समय में चलता है: हे (| S |) ~ O (n)

सेट सबसे अच्छा होगा n समाधान, प्रत्येक कश्मीर के लिए: 1..n

कश्मीर के लिए

:

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 

: आप पूरा समाधान खोजने के लिए कि मंच

पर इष्टतम विकल्प नहीं है

सिक्के किया जा सकता है फिर से इस्तेमाल किया:

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 

में जावास्क्रिप्ट:

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

आप इस सरल एल्गोरिथ्म (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; 
}