-1

異なるアイテム価格の配列があるとしましょう。 

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

次のような機能が欲しいです：

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€

}

物事を明確にするために：
値札が付いたアイテムの箱（myItemsEuro）があります。アイテムを支払いとして使用して、アイテムを購入したいです。少なくとも 1 セントを過払いすれば、相手は私の取引を受け入れます。この関数は機能するはずなので、他の人の価格 (たとえば 0.89) を渡すと、返さなければならないアイテムが返されます。これらのアイテムの組み合わせは、0.89 セント (少なくとも 0.9) を超えている必要がありますが、できるだけ低くする必要があります。

私は JS にまったく慣れていないので、アイテムのすべての組み合わせを計算し、購入価格との差が最も小さい組み合わせを使用することを考えていました。これは私には非常に複雑に思えます。すべての組み合わせを計算し、計算に使用されたアイテムを保存する方法さえわかりません。

これをもう少し効率的に達成する方法はありますか？ここで完全に機能するコードは期待していません。正しい方向に進むための少しの助けもいいでしょう。

どんな助けでも大歓迎です！:)

編集：

私自身の試みを逃して申し訳ありません。これをどのように解決すればよいかまったくわかりません。いいえ-宿題ではありません-これは、私が取り組んでいるchromeextensionの一部であるはずです! 

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

function getTradeItems(marketPrice) {

	var result = 0;

	var positions = [];

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

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

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

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

			console.log(result)
            console.log(positions)

			return positions; //return positions in the array

		}
	
	}
}

getTradeItems(1.31);

編集：

配列を並べ替えてから数値を合計しても、解決策は得られません。

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
4

2 に答える 2

0

私は取るべきいくつかの対策を提案します：

  • 小数は浮動小数点の精度の問題を引き起こす可能性があるため、最初にすべての値を整数 (セント単位の値) に変換することをお勧めします。
  • 各再帰レベルで、対応するインデックスで項目を取得するかどうかを決定する再帰検索を実行します。
  • 複数のソリューションが存在する状況を考えてみてください。そのような場合、使用するアイテムの少ないソリューションを優先したいと思うかもしれません。そのため、選択したアイテムの数を追跡する必要があります。

ここで提案する解決策は、アイテムを追加し続ける意味がないことが明らかになるとすぐに後戻りします。(再帰的検索を停止するという) この結論を引き出すことができる状況が少なくとも 2 つあります。

  • これまでに選択された値の合計がすでに目標値よりも大きい場合、(再帰を介して) さらに項目を追加しても意味がありません。
  • 位置 i に項目を追加した後、(再帰を介して) 残りのすべての項目を追加すると、合計が目標よりも小さくなることが明らかになった場合、位置 i にある項目を選択せず​​に繰り返すのは意味がありません。それは確かに目標値にも到達しないため、再帰的検索。

提案されたコードは次のとおりです。

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));

于 2016-12-18T18:37:32.120 に答える
0

ブルート フォース アプローチを使用して、アイテムのすべての組み合わせがtarget.

基本的な考慮事項は、ゼロから 2 つのvalues.lengthまでのカウンターを取得し、実際の 2 つのインデックスがビット単位の AND&を使用してカウンターの一部であるかどうかを確認することです。その場合は、インデックスから値を取得してparts配列に入れます。

次に、 を構築し、sumが配列内よりも大きいか等しいpartsかどうかを確認し、結果を結果配列に移動します。が と等しい場合、実際のとを にプッシュします。sumtargetsumresultsumresult[0].sumpartssumresult

targetこの提案はソートされていない値でも機能しますが、その値よりも大きい値が作業対象の配列に含まれていない場合は、より効率的です。

もう 1 つの欠点は、ビット演算が 32 ビットでのみ機能するという事実です。つまり、32 を超える項目を持つ配列は使用できません。

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; }

于 2016-12-18T17:09:28.350 に答える