Trouver la combinaison la plus basse de nombres prédéfinis, dont la somme est plus élevée que X

Question

disons que j'ai un tableau avec différents prix d'article.

var myItemsEuro = [0.34, 0.11, 0.5, 0.33, 0.05, 0.13, 0.23, 3.22, 1.94] 

Je voudrais avoir une fonction comme ceci:

function getTradeItems(0.89) { //The price of the item I want to buy 

    //Calculate, which of my items should be used to buy the item for 0.89€ 

    return [0, 3, 6] //The position of my items in the array, which added together equal 0.90€ 

} 

Pour éclaircir les choses:
J'ai une boîte d'articles avec pricetags sur eux (myItemsEuro). Je veux acheter un article, en utilisant mes articles comme un paiement. L'autre partie acceptera mon commerce si je paye au moins un cent. La fonction devrait fonctionner, donc je peux passer le prix de l'autre gars (0.89 par exemple) et il revient, quels articles je vais devoir donner. La combinaison de ces éléments doit être supérieure à 0,89 cents (au moins 0,9), mais devrait être aussi faible que possible! Je suis assez nouveau à JS, et je pensais à calculer chaque combinaison de mes articles, puis d'utiliser celui qui a la différence la plus faible pour le prix d'achat. Cela me semble vraiment compliqué et je ne sais même pas comment je le ferais calculer chaque combinaison et aussi enregistrer quels éléments ont été utilisés pour le calcul.

Y at-il un moyen d'y parvenir un peu plus efficace? Je ne m'attends pas vraiment à un code qui fonctionne parfaitement ici, un peu d'aide pour aller dans la bonne direction serait également bien.

Toute aide est appréciée! :)

---

Edit:

Désolé pour avoir manqué ma tentative. C'est juste que je n'ai aucune idée de comment je devrais résoudre ça du tout. Et non - pas de devoirs - ceci est censé faire partie d'une extension chromatique sur laquelle je travaille!

var myItemsEuro = [0.34, 0.11, 0.5, 0.33, 0.05, 0.13, 0.23, 3.22, 1.94] 
 

 
function getTradeItems(marketPrice) { 
 

 
\t var result = 0; 
 

 
\t var positions = []; 
 

 
\t for(i = 0; i < myItemsEuro.length; i++) { 
 

 
\t \t result += myItemsEuro[i]; //add numbers from the array 
 

 
\t \t positions.push(i); //save the used numbers position 
 

 
\t \t if(result > marketPrice) { //if result is greater than marketPrice... 
 

 
\t \t \t console.log(result) 
 
      console.log(positions) 
 

 
\t \t \t return positions; //return positions in the array 
 

 
\t \t } 
 
\t 
 
\t } 
 
} 
 

 
getTradeItems(1.31);

---

Edit:

Tri le tableau, puis en ajoutant des numéros ne donne pas une solution.

var x = 1.18; 

    //Sorted by numbers 
var myItemsEuro = [0.05, 0.11, 0.13, 0.20, 0.35, 0.50, 0.60, 0.69, 0.75]; 

    //Add together and stop when sum > x: 
0.05 + 0.11 + 0.13 + 0.20 + 0.35 + 0.50 = 1.34 

    //Best solution would be adding [6] and [8] from the array 
0.50 + 0.69 = 1.19 

Answer 1

Vous pouvez utiliser une approche de force brute et de tester toutes les combinaisons des éléments si elles sont supérieures ou égales du target.

La prise en compte de base consiste à prendre un compteur de zéro à 2 ^{values.length} et vérifier si l'indice réel fait partie du compteur avec une bitwise AND &. Si c'est le cas, prenez la valeur de l'index et placez-la dans le tableau parts.

ensuite construire le sum du parts et vérifier si sum est supérieur ou égal de target et peut-être plus petit que sum dans le tableau result, puis déplacez le résultat au tableau de résultat.Si sum est égal à result[0].sum, appuyez sur les parts et sum sur result.

Cette proposition fonctionne avec des valeurs non triées, mais pourrait être plus efficace si les valeurs qui sont supérieures à la valeur target ne sont pas incluses dans la matrice sur laquelle travailler.

Un autre inconvénient est le fait que bitwise arithmetic fonctionne uniquement avec 32 bits, ce qui signifie que les tableaux contenant plus d'éléments que 32 ne sont pas utilisables.

var values = [0.34, 0.11, 0.5, 0.33, 0.05, 0.13, 0.23, 3.22, 1.94], 
 
    target = 0.90, 
 
    i, 
 
    l = 1 << values.length, 
 
    result = [], 
 
    parts, 
 
    sum; 
 

 
for (i = 0; i < l; i++) { 
 
    parts = values.filter(function (_, j) { 
 
     return i & 1 << j; 
 
    }); 
 
    sum = parts.reduce(function (a, b) { return a + b; }, 0); 
 
    if (sum >= target) { 
 
     if (!result.length || sum < result[0].sum) { 
 
      result = [{ parts: parts, sum: sum }]; 
 
      continue; 
 
     } 
 
     if (sum === result[0].sum) { 
 
      result.push({ parts: parts, sum: sum }); 
 
     } 
 
    } 
 
} 
 

 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Je suggère quelques mesures à prendre:

• nombres fractionnaires peuvent causer à virgule flottante des problèmes de précision, il est donc préférable d'abord convertir chaque valeur à un nombre entier (ie valeur en cents)
• Effectuez une recherche récursive, où à chaque niveau de récursion, vous déciderez de prendre ou non l'élément à l'index correspondant. Pensez aux situations où vous pourriez avoir plusieurs solutions: peut-être dans ces cas vous voulez donner la priorité aux solutions qui utilisent moins d'éléments. Vous devez donc garder une trace du nombre d'éléments sélectionnés.

La solution que je propose ici va revenir en arrière dès qu'il est clair qu'il n'y a aucun sens à poursuivre l'ajout d'éléments. Il y a au moins deux situations où vous pouvez tirer cette conclusion (d'arrêter la recherche récursive):

• Lorsque la somme des valeurs sélectionnées jusqu'à présent est déjà supérieure à la valeur cible, alors il n'y a aucun sens à ajouter more items (via récursion)
• Si après avoir ajouté un objet à la position i, il devient clair que l'addition de tous les éléments restants (via la récursivité) conduit à une somme inférieure à la cible, alors cela n'a aucun sens de ne pas sélectionnez l'élément à la position i, et répétez la recherche récursive, car cela n'atteindra certainement pas non plus la valeur cible.

Voici le code suggéré:

function getTradeItems(target, items) { 
 
    var best = -1e20, // should be maximised up to -1 if possible 
 
     bestTaken = [], // indices of the best selection 
 
     bestCount = 0, // number of selected items in best solution 
 
     // Multiply all amounts by 100 to avoid floating point inaccuracies: 
 
     cents = items.map(euro => Math.round(euro * 100)); 
 
    function recurse(target, i, count) { 
 
     if (target < 0) { // Found potential solution 
 
      // Backtrack if this is not better than the best solution 
 
      // found so far. If a tie, then minimise the number of selected items 
 
      if (target < best || 
 
       target === best && count > bestCount) return false; 
 
      best = target; 
 
      bestTaken = []; 
 
      bestCount = count; 
 
      return true; 
 
     } 
 
     // Give up when there's not enough item value available 
 
     if (i >= cents.length) return null; 
 
     // Include the item at index i: 
 
     var res1 = recurse(target - cents[i], i+1, count+1); 
 
     // If we could not reach the target, don't lose time retrying 
 
     // without this item: 
 
     if (res1 === null) return null; 
 
     // Exclude the item at index i: 
 
     var res0 = recurse(target, i+1, count); 
 
     // If neither led to a solution... 
 
     if (!res0 && !res1) return false; 
 
     // If the best was to include the item, remember that item 
 
     if (!res0) bestTaken.push(i); 
 
     return true; 
 
    } 
 
    recurse(Math.round(target * 100), 0); 
 
    return bestTaken.reverse(); 
 
} 
 

 
// Sample input 
 
var myItemsEuro = [0.05, 0.11, 0.13, 0.20, 0.35, 0.50, 0.60, 0.69, 0.75]; 
 
var x = 1.18 
 
// Get the best item selection 
 
var result = getTradeItems(x, myItemsEuro); 
 
// Output result 
 
console.log('Selected: ', result.join()); // 5, 7 
 
// Show corresponding sum: (1.19) 
 
console.log('Sum: ', result.reduce((sum, i) => sum + myItemsEuro[i], 0).toFixed(2));