我需要一些帮助来为正在创建的应用程序编写函数。
假设我有一个由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个数组。这些数组代表以下任务:
我需要一个可以确定我是否有足够的对象来完成所有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;
}
}
}
执行深度优先搜索是一种解决方案。
在该函数中,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] 删除。
我来说两句