需要帮助编写函数

XtevensChannel

我需要一些帮助来为正在创建的应用程序编写函数。

假设我有一个由5个对象组成的数组。

var pool = [
    {"color":"Pink"},
    {"color":"Pink"},
    {"color":"Green"},
    {"color":"Orange"},
    {"color":"Orange"}
];

我也有一个定义要完成任务的数组。

var tasks = [
    [
        {
            "amount": 1,
            "color": "Orange"
        },
        {
            "amount": 1,
            "color": "Pink"
        }
    ],
    [
        {
            "amount": 2,
            "color": "Green"
        },
        {
            "amount": 1,
            "color": "Orange"
        }
    ],
    [
        {
            "amount": 1,
            "color": "Orange"
        }
    ]
];

任务数组包含3个数组。这些数组代表以下任务:

  1. 从池中删除1个粉红色对象或1个橙色对象。
  2. 从池中删除2个绿色对象或1个橙色对象。
  3. 从池中删除1个橙色物体。

我需要一个可以确定我是否有足够的对象来完成所有3个任务的函数。必须按顺序完成任务。

因此,对于第一个任务,我们将检查池中是否有1个粉红色对象或1个橙色对象。池中有2个粉红色对象和2个橙色对象,因此我们知道可以完成此任务。

对于第二项任务,我们检查是否要从池中删除2个绿色对象或1个橙色对象。我们只有1个绿色对象,因此不能删除2个绿色对象。我们唯一的选择是从池中删除1个橙色对象。我们考虑过为第一个任务删除一个Orange对象,但是如果我们为该任务删除一个Orange对象,则该任务仍然可以完成。

对于第三项任务,我们检查是否要删除1个橙色对象。我们有2个,但我们知道第二个任务必须删除1个Orange对象。这也意味着我们无法删除第一个任务的Orange对象。

因此最后,我们知道可以为第一个任务删除的唯一对象是2个Pink对象之一。第二项任务必须删除其中一个Orange对象,而第三项必须删除另一个Orange对象。

在尝试完成任何任务之前,我需要编写一个可以确定所有逻辑的函数。

以下函数canDoTasks不太起作用,因为它没有考虑先前的任务是否需要使用任何对象。

function canDoTasks1() {
    outerloop:
    for (var i = 0; i < tasks.length; i++) {
        var mandatory_task = tasks[i];
        for (var j = 0; j < mandatory_task.length; j++) {
            var optional_task = mandatory_task[j];
            var amount = countRemainingObjects(pool, optional_task.color);
            if (amount >= optional_task.amount) {
                continue outerloop;
            }
        }
        return false;
    }
    return true;
}

function countRemainingObjects(arr, color) {
    var total = 0;
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].color == color) {
            total++;
        }
    }
    return total;
}

下一个函数canDoTasks2也不起作用,因为它在确定每个任务需要删除哪些对象方面做得不够聪明。

function canDoTasks2() {
    var pool_copy = pool.slice();
    outerloop:
    for (var i = 0; i < tasks.length; i++) {
        var mandatory_task = tasks[i];
        for (var j = 0; j < mandatory_task.length; j++) {
            var optional_task = mandatory_task[j];
            var amount = countRemainingObjects(pool_copy, optional_task.color);
            if (amount >= optional_task.amount) {
                removeFromPool(pool_copy, optional_task.color);
                continue outerloop;
            }
        }
        return false;
    }
    return true;
}

function removeFromPool(arr, color) {
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].color == color) {
            arr.splice(i, 1);
            return;
        }
    }
}
牛ob

执行深度优先搜索是一种解决方案。

在该函数中,findTheWay()我们将池重新排列成字典,告诉我们当前每种颜色有多少种可用。然后,我们使用它对任务列表进行深度优先搜索,以找到完成任务的第一种方式。

findTheWay() 返回任务列表中各步骤的索引数组。

const pool = [
  {"color":"Pink"},
  {"color":"Pink"},
  {"color":"Green"},
  {"color":"Orange"},
  {"color":"Orange"}
];

const tasks = [
  [
    { "amount": 1, "color": "Orange" },
    { "amount": 1, "color": "Pink" }
  ],
  [
    { "amount": 2, "color": "Green" },
    { "amount": 1, "color": "Orange" }
  ],
  [
    { "amount": 1, "color": "Orange" }
  ]
];

const findTheWay = (items, tasks) => {
  // Collate the items into a color:count dictionary
  const pool = {};
  // Only care about the items that could be handled by the task list
  tasks.forEach(t => t.forEach(c => c.color in pool ? null : pool[c.color] = 0));
  // Count up the items
  items.forEach(i => i.color in pool ? pool[i.color]++ : null);
  
  // Prep a choices array that matches up with the tasks array
  const choice = new Array(tasks.length).fill(0);
  var idx = 0;
  
  // Perform the depth-first search
  while(true) {
    // If we've run out of options for a particular step, rewind to the 
    // previous step and choose its next option. If we rewind past the 
    // beginning of the list, there are no solutions.
    if(choice[idx] >= tasks[idx].length) {
      if(--idx < 0) break;
      const subtask = tasks[idx][choice[idx]];
      pool[subtask.color] += subtask.amount;
      choice[idx]++;
      continue;
    }
    
    // If the current choice in the current step is feasible, move to 
    // the next step. If we move past the end of the list, we've found
    // a solution.
    const subtask = tasks[idx][choice[idx]];
    if(pool[subtask.color] >= subtask.amount) {
      pool[subtask.color] -= subtask.amount;
      if(++idx >= choice.length) break;
      choice[idx] = 0;
      continue;
    }
    
    // This choice for this step didn't work out so move on to the 
    // next option.
    choice[idx]++;
  }

  if(idx < 0) return null;
  return choice;
};

const thisIsTheWay = findTheWay(pool, tasks);
console.log(thisIsTheWay);
console.log(thisIsTheWay.map((v,i) => tasks[i][v]));

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章