-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）。我想购买一件物品，用我的物品作为付款。如果我多付至少一美分，对方将接受我的交易。该功能应该可以工作，所以我可以将其他人的价格传递给它（例如 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

您可以使用蛮力方法并测试项目的所有组合，如果它们大于或等于target.

基本考虑是取一个从零到 2 values.length的计数器，并使用按位 AND检查实际的 2索引是否是计数器的一部分。如果是这样，则从索引中获取值并将其放入数组中。&parts

然后构建sumofparts并检查是否sum大于或等于target并可能小于数组sum，result然后将结果移动到结果数组。如果sum等于，则将实际和result[0].sum推到。partssumresult

target此建议适用于未排序的值，但如果值大于该值不包含在要处理的数组中，则可能更有效。

另一个缺点是，按位算术仅适用于 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 回答
0

我建议采取一些措施：

  • 小数会导致浮点精度问题，因此最好先将每个值转换为整数（即​​以美分为单位的值）
  • 执行递归搜索，在每个递归级别，您将决定是否在相应索引处获取项目。
  • 想想您可能有多个解决方案的情况：也许在这些情况下，您希望优先考虑使用较少项目的解决方案。因此，您需要跟踪所选项目的数量。

我在这里提出的解决方案将在很明显继续添加项目没有意义时立即回溯。至少有两种情况可以得出这个结论（停止递归搜索）：

  • 当到目前为止选择的值的总和已经大于目标值时，添加更多项（通过递归）是没有意义的
  • 如果在位置 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 回答