根据大小和预算两个因素创建数组

Question

我有一个大约 500 个项目的数组，每个项目都包含一个随机成本属性。如何创建一个采用大小和预算两个参数的函数。大小决定了新数组应该有多大，预算决定了新数组中可以包含的最大项目成本量。它应该始终尽可能接近预算和大小，并允许尽可能多次地重复使用项目，但也应该尽可能随机。

这是我当前的代码，但是我在满足这两个要求时遇到问题，并且对基于试验和错误的解决方案不满意。我曾尝试研究背包问题来尝试实现类似类型的算法，但说实话，数学并不是我的强项。

  function getItems(budget: any, itemCount: any, items: any) {
    let selectedItems: any = [];
    let remainingBudget = budget;
    let maximumRetries = 100000;

    if (
      budget <= 0 ||
      itemCount <= 0 ||
      !Array.isArray(items) ||
      items.length === 0
    ) {
      console.log("[useRoll] Invalid Parameters");
      return { remainingBudget, selectedItems };
    }

    while (remainingBudget > budget / 10 && maximumRetries > 0) {
      maximumRetries--;

      while (selectedItems.length < itemCount) {
        if (remainingBudget < budget / 10) {
          selectedItems = selectedItems.sort(
            (a: any, b: any) => b.cost - a.cost,
          );

          const removedItemCost = selectedItems[0].cost;
          selectedItems.splice(1, selectedItems.length);
          remainingBudget += removedItemCost;
        }

        let availableItems = [
          ...items.filter((item: any) => item.cost <= remainingBudget),
        ];
        const randomIndex = Math.floor(
          Math.random() * availableItems.length - 1,
        );
        const selectedItem = availableItems[randomIndex];

        if (selectedItem && selectedItem.cost) {
          const itemCost = selectedItem.cost;

          if (itemCost <= remainingBudget) {
            selectedItems.push(selectedItem);
            remainingBudget -= itemCost;
          }
        } else {
          availableItems.splice(randomIndex, 1);
        }
      }
    }

    if (maximumRetries === 0) console.log("Maximum Retries reached");

    return { remainingBudget, selectedItems };
  }

Answer 1

您似乎想要创建一系列具有特定大小和预算约束的项目，同时最大化随机性并尽可能满足预算。您当前的代码有些复杂，正如您提到的，它不是很有效并且可以改进。

为了实现您的目标，您可以使用不同的方法。您可以创建一个函数，以迭代方式随机选择项目，同时跟踪剩余预算和所需的数组大小。这是您的函数的简化和改进版本：

    function getItems(budget, itemCount, items) {
      let selectedItems = [];
      let remainingBudget = budget;
    
      if (
        budget <= 0 ||
        itemCount <= 0 ||
        !Array.isArray(items) ||
        items.length === 0
      ) {
        console.log("[useRoll] Invalid Parameters");
        return { remainingBudget, selectedItems };
      }
    
      while (selectedItems.length < itemCount && remainingBudget > 0) {
        const randomIndex = Math.floor(Math.random() * items.length);
        const selectedItem = items[randomIndex];
        const itemCost = selectedItem.cost;
    
        if (itemCost <= remainingBudget) {
          selectedItems.push(selectedItem);
          remainingBudget -= itemCost;
        }
      }
    
      if (remainingBudget > 0) {
        console.log("Budget not fully utilized");
      }
    
      return { remainingBudget, selectedItems };
    }

此代码将从

items

数组中随机选择项目，直到达到所需的

itemCount

或耗尽预算。它更简单，并且应该在尝试满足您的预算限制的同时提供更随机的项目分配。请记住，这种方法可能并不总是生成大小完全相同的数组

itemCount

或利用整个预算，但它应该在保持随机性的同时尽可能接近。