回溯问题 #19
Comments
有重复元素的子集问题var subsetsWithDup = function(nums) {
if (!Object(nums).length) {
return [];
}
nums.sort();
var result = [];
backtrack(result, [], nums, 0, {});
return result;
};
function backtrack(result, candidate, nums, i, hash) {
if (i > nums.length) {
return;
}
if (!hash[candidate]) {
//在结果中进行防止重复
result.push(candidate.concat()); //没有长度限制
hash[candidate] = 1;
}
// for (var i = start; i < n; i++) {
candidate.push(nums[i]); //试探
backtrack(result, candidate, nums, i + 1, hash);
candidate.pop(); //不管成功与否，退回上一步
backtrack(result, candidate, nums, i + 1, hash);
// }
}
console.log(subsetsWithDup([4, 4, 4, 1, 4])); |
摆火柴棍function makesquare(nums) {
if (Object(nums).length < 4) {//如果火柴数量不足4，肯定摆不出正方形
return false;
}
var sides = [[], [], [], []];
var total = nums.reduce(function(prev, el) {
return prev + el;
}, 0);
if (total % 4) { //如果不能被4整除
return false;
}
nums.sort();
var max = total / 4, curr = [0, 0, 0, 0],end = nums.length;
function backtrack(sides, nums, start, curr, max) {
if (start >= end) {
return (
curr[0] == max &&
curr[1] == max &&
curr[2] == max &&
curr[3] == max
);
} else {
for (var i = 0; i < 4; i++) {
if (curr[i] + nums[start] > max) {
continue;
}
sides[i].push(nums[start]); //这个可以不要
curr[i] += nums[start];
if (backtrack(sides, nums, start + 1, curr, max)) {
return true;
}
sides[i].pop(); //这个可以不要
curr[i] -= nums[start];
}
}
return false;
}
var result = backtrack(sides, nums, 0, curr, max);
console.log(JSON.stringify(sides), result);
return result;
}
makesquare([4, 3, 3, 2, 2, 1, 1]); |
子集问题的构建空间树法在网上，回溯算法也会与一种叫解空间树的数据结构联系在一起。因为我们遍历题目给出的元素过程中，会产生许多解，这些解其实是形成一棵树。 以第1题为例，其树结构是这样的： ![image_1dlkmg1a9tvv19di1vru1c16188bm.png-41.2kB][2] 因此我们只要一层层构建这棵空间树，拿到最后一层就是解。 function subsets(nums) {
if (!Object(nums).length) {
return []
}
nums.sort()
var root = [], level = [root], newLevel = []
for (var i = 0; i < nums.length; i++) {
for (let j = 0; j < level.length; j++) {
root = level[j];
var node = root.concat(nums[i])
root.left = node; //让它更像二叉树
newLevel.push(node)
var node = root.concat()
root.right = node;//让它更像二叉树
newLevel.push(node);
}
level = newLevel;
newLevel = [];
}
return level; //返回最后一层
};
subsets([1, 2, 3]);
console.log(a)第2题，因为它的元素存在重复，因此必须结果集中的子数组存在重复，因此我们只要在上面的解法中做一次去重操作就行了。 第3题，有重复元素的子集问题, 由于我们的空间树是每层放入数组的不同元素，因此无法用这构建树的方式解决它。 第4题，无重复元素的子集问题, 可以，但是结果集不是集中在最后一层，而是分布在树的各个位置，并且在构建过程中，我们可以裁剪无效分支。 function combinationSum(nums, target) {
if (!Object(nums).length) {
return []
}
nums.sort()
var root = [], level = [root], newLevel = []
root.sum = 0;
var result = [], hash = {}
for (var i = 0; i < nums.length; i++) {
for (let j = 0; j < level.length; j++) {
root = level[j];
var node = root.concat(nums[i])
var sum = root.sum + nums[i]
if (sum === target) {
if (!hash[node]) {//去重
hash[node] = 1;
result.push(node)
}
continue
}
if (sum < target) {
root.left = node; //让它更像二叉树
node.sum = sum
newLevel.push(node)
}
var node = root.concat()
root.right = node; //让它更像二叉树
node.sum = root.sum;
newLevel.push(node);
}
level = newLevel;
newLevel = [];
}
return level
};
combinationSum([10, 1, 2, 7, 6, 1, 5], 8);问题5，装载问题，我们的集装箱放了这条船就不能放另一条，说明它们不在同一分支上。又由于我们需要装完所有箱子，因此它们只会出现在最后一层。再仔细观察，每个子集是呈左右对称分布的。因此我们拿到最后一层，然后左右同时取两个元素进行比较就能得出结果 ![image_1dlmq8mvbg3gv6ur8ue9u1al81s.png-21.2kB][3] function sum(arr) {
return arr.reduce(function(prev, el) {
return prev + el;
}, 0);
}
function load(c1, c2, goods) {
if (!Object(goods).length) {
return [];
}
goods.sort();
var root = [], level = [root],
//略掉构建空间树的部分，读者自行补完
var n = level.length， cn = goods.length;
for (var i = 0; i < n / 2; i++) {
var boat1 = level[i];
var boat2 = level[n - i - 1];
if (
boat1.length + boat2.length == cn &&
sum(boat1) <= c1 && sum(boat2) <= c2
) {
return [boat1, boat2];
}
}
return []; //返回最后一层
}
load(50, 50, [20, 30, 25]);问题6, 同上，就是子数组多一点而已。 |
|
组合问题 给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 注意只要装k个 function combine(n, k) {
var result = [], condidate = []
function backtrack(start) {
if (condidate.length == k) {
result.push(condidate.concat())
} else {
for (var i = start; i <= n; i++) {
condidate.push(i)
backtrack(i + 1)
condidate.pop()
}
}
}
backtrack(1);
return result;
}
console.log(combine(4, 2)) |
括号问题function parentheses(n) {
var leftnum = n, rightnum = n;//左括号和右括号都各有n个
var result = []
function backtrack(sublist, leftnum, rightnum) {
if (leftnum == 0 && rightnum == 0) {//结束
result.push(sublist);
}
if (rightnum > leftnum) {//选择和条件。对于不同的if顺序，输出的结果顺序是不一样的，但是构成一样的解空间
backtrack(sublist + ")", leftnum, rightnum - 1);
}
if (leftnum > 0) {
backtrack(sublist + "(", leftnum - 1, rightnum);
}
}
backtrack("", leftnum, rightnum);
console.log(result);
}
parentheses(3) |
有重复元素的子集问题给定一个可能有重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。注意：结果集不能包含重复的子集。 与上题只有一点差别，但它只是对候选集做出限制，即结果集中不能出现两个[1,2]数组。这个我们可以使用hash去重。 var subsetsWithDup = function (nums) {
if (!Object(nums).length) {
return [];
}
nums.sort((a, b) => a - b)
var result = [], candidate = [], end = nums.length, hash = {};
function backtrack(start) {
if (!hash[candidate]) { //在结果中进行防止重复
result.push(candidate.concat());//没有长度限制
hash[candidate] = 1;
}
for (var i = start; i < end; i++) {
candidate.push(nums[i]) //试探
backtrack(i + 1);
candidate.pop(); //不管成功与否，退回上一步
}
}
backtrack(0);
return result;
};
subsetsWithDup([4, 4, 4, 1, 4])当然，我们还可以在递归函数的for循环中做去重，感兴趣的同学可以试一下。 |
|
装船问题 function boatLoad(goods, c1, c2) {
var allocation = new Array(goods.length).fill(0); //用于表示它分配到哪一条船
var result = []
var boatsNum = 0; //总共有多少条船
var curLoad = [0]; //索引0没有用
var maxLoad = [0]; //索引0没有用
//初始化数据
for (var i = 1; i < arguments.length; i++) {
curLoad[i] = 0;
maxLoad[i] = arguments[i]
boatsNum++;
}
function backtrack(start, isFull) {//start表示集装箱的编号
if (start >= goods.length) {
if (!isFull) {
return false
}
for (let i = 1; i <= boatsNum; i++) {
if (curLoad[i] > maxLoad[i] || curLoad[i] > maxLoad[i]) {
return false;//不能超过该船的最大装载量
}
}
result = allocation.concat()
return true
} else {
for (let i = 1; i <= boatsNum; i++) {
allocation[start] = i; //1装在船1; 2装在船2
if (curLoad[i] + goods[start] <= maxLoad[i]) {
curLoad[i] += goods[start]
if (backtrack(start + 1, i == boatsNum)) {
return true
}
curLoad[i] -= goods[start]
}
}
}
}
backtrack(0)
// console.log(allocation, '!!!')
return allocation
}
var result4 = 0;
for (var i = 0; i < 500; i++) {
var time = new Date();
boatLoad([10, 30, 10, 25, 20], 50, 50);
result4 += new Date() - time;
}
console.log("load4", result4 / 500);
console.log(boatLoad([10, 50, 10, 20, 20, 10], 50, 50, 50)) |
批处理作业调度题目 function swap(x, t, j) {
var temp = x[t];
x[t] = x[j];
x[j] = temp;
}
function schedule2() {
var work = [[0, 0], [2, 1], [3, 1], [2, 3]]
//可以分段赋值也可以,逐个赋值用,隔开
var n = 3;
var best = 1000;
var order = [0, 1, 2, 3];//排列树的初始化
var flow = [0, 0, 0, 0]
var bestFlow = []
function backTrack(t) {
if (t > n) {
var sum = 0;
for (var i = 1; i <= n; i++) {
flow[i] = flow[i - 1] + Math.abs(work[order[i]][0] - work[order[i - 1]][1]) + work[order[i]][1];
sum += flow[i];
}
if (sum < best) {
best = sum;
bestFlow = order.concat()
}
}
else {
for (var i = t; i <= n; ++i) {
swap(order, t, i);
backTrack(t + 1);
swap(order, t, i);
}
}
}
backTrack(1)
console.log(bestFlow, best)
}
function schedule3(n, time1, time2) {
var work = []
for (var i = 0; i < n; i++) {
work[i] = [time1[i], time2[i]]
}
var condidtate = [] //排列树最开始的解为0，1，2
//机器1,2完成某个作业的结束时间
var flow1 = [], flow2 = [];
var best = Infinity, bestFlow = [];
//我们使用hash实现全排列，否则需要引入两个swap方法
var hash = {}
function backTrack(start) {
if (start == n) {
for (var i = 0; i < n; i++) {
var index = condidtate[i];
flow1[i] = (flow1[i - 1] || 0) + work[index][0]
flow2[i] = Math.max((flow2[i - 1] || 0) + flow1[i]) + work[index][1]
}
var sum = flow2[n - 1]
if (sum < best) {
best = sum;
bestFlow = condidtate.concat()
}
} else {
for (var i = 0; i < n; i++) {
if (!hash[i]) {
condidtate.push(i)
hash[i] = 1
backTrack(start + 1);
condidtate.pop();
hash[i] = 0
}
}
}
}
backTrack(0)
console.log("最小完成时间和", best)
console.log("最佳调度顺序为", bestFlow)
return [best, bestFlow]
}
schedule3(3, [2, 3, 2], [1, 1, 3]) |
独立任务最优调度（双机调度）问题 |
01背包问题function knapsack01(n, weights, values, capacity) {
var allocation = new Array(n).fill(0); //表示它选中了没有;
var curValue = 0,
curWeight = 0,
maxValue = 0,
maxWeight = 0,
result = [];
function backtrack(start) {//start为物号的编号
if (start == n) {
//这只是其中一个候选项
if (curValue > maxValue) {
maxValue = curValue;
maxWeight = curWeight;
result = allocation.concat();
}
} else {
for (var i = 0; i < 2; i++) {
if (curWeight + i * weights[start] <= capacity) {
allocation[start] = i; //0不装，1装
curWeight += i * weights[start];
curValue += i * values[start];
backtrack(start + 1);
curWeight -= i * weights[start];
curValue -= i * values[start];
}
}
}
}
backtrack(0);
console.log(maxValue, maxWeight, allocation);
return [maxValue, allocation];
}
knapsack01(5, [10, 20, 30, 40, 50], [20, 30, 65, 40, 60], 100); |
数独问题你一定听说过“数独”游戏。 005300000 程序应该输出： 再例如，输入: 程序应该输出: 数独游戏使用深度优先搜索的方法是比较方便的，可以搜出数独的所有合法的解（使用其他的方法来解决是非常困难的或者是不可能的） function solveSudoku(board) {
var result = []
function backtrack(x, y) {
if (x == 9) {
board.forEach(function (row) {
result.push(row.concat())
})
return true
} else {
if (board[x][y] == '.') {
for (var i = 1; i <= 9; i++) {
if (check(board, x, y, i)) {
board[x][y] = i + ""
if (backtrack(x + Math.floor((y + 1) / 9), (y + 1) % 9)) {
return true
}
}
}
board[x][y] = '.';
} else {
if (backtrack(x + Math.floor((y + 1) / 9), (y + 1) % 9)) {
return true
}
}
}
}
function check(board, x, y, k) {
for (var i = 0; i < 9; i++) {
//我们想在board[x][y] 中填入k， 结果在board[x][i] 或 board[i][y] 出现相同的k
if (board[x][i] == k + '' || board[i][y] == '' + k) {
return false;
}
}
//检查九宫格
var xx = Math.floor(x / 3)
var yy = Math.floor(y / 3)
for (var i = xx * 3; i < (xx + 1) * 3; i++) {
for (var j = yy * 3; j < (yy + 1) * 3; j++) {
if (board[i][j] == '' + k) {
return false;
}
}
}
return true;
}
backtrack(0, 0)
console.log(JSON.stringify(result))
return result;
}
solveSudoku(
[["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]]
) |
function solveSudoku(board) {
var result = []
function backtrack(x, y) {
if (x == 9) {
board.forEach(function (row) {
result.push(row.concat())
})
return true
} else {
if (board[x][y] == '.') {
for (var i = 1; i <= 9; i++) {
if (check(board, x, y, i + '')) {
board[x][y] = i + ""
if (backtrack((y == 8 ? x + 1 : x), (y == 8 ? 0 : y + 1))) {
return true
}
}
}
board[x][y] = '.';
} else {
if (backtrack((y == 8 ? x + 1 : x), (y == 8 ? 0 : y + 1))) {
return true
}
}
}
}
function check(board, x, y, k) {
for (var i = 0; i < 9; i++) {
//我们想在board[x][y] 中填入k， 结果在board[x][i] 或 board[i][y] 出现相同的k
if (board[x][i] == k || board[i][y] == k) {
return false;
}
}
//检查九宫格
var xx = Math.floor(x / 3)
var yy = Math.floor(y / 3)
for (var i = xx * 3; i < (xx + 1) * 3; i++) {
for (var j = yy * 3; j < (yy + 1) * 3; j++) {
if (board[i][j] == k) {
return false;
}
}
}
return true;
}
backtrack(0, 0)
console.log(JSON.stringify(result))
return result;
} |
找字符串leetcode 212 Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. function findWords(board, words) {
var visited = new Array(board.length).fill(0).map(function (el, i) {
return new Array(board[0].length).fill(false)
})
var res = []
var set = new Set();
for (var word of words) {
set.add(word);
}
function backtrack(cur, x, y) {
if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y]) {
return;
}
var c = board[x][y];
if (set.has(cur + c)) {
res.push(cur + c);
set.delete(cur + c);
}
visited[x][y] = true;
backtrack(cur + c, x + 1, y);
backtrack(cur + c, x - 1, y);
backtrack(cur + c, x, y + 1);
backtrack(cur + c, x, y - 1);
visited[x][y] = false;
}
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[0].length; j++) {
backtrack("", i, j);
}
}
return res;
}
var board = [
['o', 'a', 'a', 'n'],
['e', 't', 'a', 'e'],
['i', 'h', 'k', 'r'],
['i', 'f', 'l', 'v']
],
words = ["oath", "pea", "eat", "rain"]
console.log(findWords(board, words)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
装载问题
有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中每个集装箱重量为
[20, w1, ..wi]， 总重量不会大于c1 + c2。 问是否有一个合理的装载方案， 可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。解法1， 先对船1求最优解，然后将剩下的集装箱丢给船2。这样也网上最流行的解法，CSDN上到处是这个解法的copy，真是醉了。比如下图，看到cw， bestw就知道是出自这一个思路。
解法2， 构建解空间树，然后我们在最后一层，从两端起收集可能的解。
解法3，这是我从leetcode的摆火柴棍的一个外国解法学到，只不过原题是四条边，需要4个子数组，这里两条船，需要两个子数组。
The text was updated successfully, but these errors were encountered: