1. 写一个程序，使用暴力技巧来寻找最长公共子串。

function lcsBruteForce(word1, word2) {var maxLength = 0;var longestSubstring = "";for (var i = 0; i < word1.length; i++) {for (var j = i + 1; j <= word1.length; j++) {var substring = word1.substring(i, j);if (word2.includes(substring) && substring.length > maxLength) {maxLength = substring.length;longestSubstring = substring;}}}return longestSubstring;
}
var word1 = "ABABC";
var word2 = "BABCA";
console.log(lcsBruteForce(word1, word2));

2. 写一个程序，允许用户改变背包问题的约束条件，以便于观察条件的变化对结果的影 响。比如，你可以改变背包的容量、物品的价值，或物品的重量。每次最好只改一个约 束条件。

function knapsack(capacity, size, value, n) { if (n == 0 || capacity == 0) { return 0; } if (size[n - 1] > capacity) { return knapsack(capacity, size, value, n - 1); } else { return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1)); } 
} function dKnapsack(capacity, size, value, n) { var K = []; for (var i = 0; i <= capacity + 1; i++) { K[i] = []; } for (var i = 0; i <= n; i++) { for (var w = 0; w <= capacity; w++) { if (i == 0 || w == 0) { K[i][w] = 0; } else if (size[i - 1] <= w) { K[i][w] = max(value[i - 1] + K[i-1][w-size[i-1]], K[i-1][w]); } else { K[i][w] = K[i - 1][w]; } console.log(K[i][w] + " "); } } return K[n][capacity]; 
}

3. 使用贪心算法找零钱，不过这次不允许使用 10 美分，假设要找的零钱一共是 30 美分， 请尝试找到一个解。这个解是最优解吗？

function makeChange(origAmt, coins) { var remainAmt = 0; if (origAmt % .25 < origAmt) { coins[3] = parseInt(origAmt / .25); remainAmt = origAmt % .25; origAmt = remainAmt; } 
/*	if (origAmt % .1 < origAmt) { coins[2] = parseInt(origAmt / .1); remainAmt = origAmt % .1; origAmt = remainAmt; } 
*/	if (origAmt % .05 < origAmt) { coins[1] = parseInt(origAmt / .05); remainAmt = origAmt % .05; origAmt = remainAmt; } coins[0] = parseInt(origAmt / .01);
} function showChange(coins) { if (coins[3] > 0) { console.log("25 美分的数量 - " + coins[3] + " - " + coins[3] * .25); } 
/*	if (coins[2] > 0) { console.log("10 美分的数量 - " + coins[2] + " - " + coins[2] * .10); } 
*/	if (coins[1] > 0) { console.log("5 美分的数量 - " + coins[1] + " - " + coins[1] * .05); } if (coins[0] > 0) { console.log("1 美分的数量 - " + coins[0] + " - " + coins[0] * .01); } 
} var origAmt = .3; 
var coins = []; 
makeChange(origAmt, coins); 
showChange(coins);

本章实验代码：

function recurFib(n) { if (n < 2) { return n; } else { return recurFib(n-1) + recurFib(n-2); } 
} function dynFib(n) { var val = []; for (var i = 0; i <= n; ++i) { val[i] = 0; } if (n == 1 || n == 2) { return 1; } else { val[1] = 1; val[2] = 2; for (var i = 3; i <= n; ++i) { val[i] = val[i-1] + val[i-2]; } return val[n-1]; } 
}function iterFib(n) { var last = 1; var nextLast = 1; var result = 1; for (var i = 2; i < n; ++i) { result = last + nextLast; nextLast = last; last = result; } return result; 
}function lcs(word1, word2) { var max = 0; var index = 0; var lcsarr = new Array(word1.length + 1); for (var i = 0; i < word1.length + 1; ++i) { lcsarr[i] = new Array(word2.length + 1); for (var j = 0; j < word2.length + 1; ++j) { lcsarr[i][j] = 0; } } for (var i = 1; i <= word1.length; ++i) { for (var j = 1; j <= word2.length; ++j) { if (word1[i - 1] == word2[j - 1]) { lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1; if (max < lcsarr[i][j]) { max = lcsarr[i][j]; index = i; } }else { lcsarr[i][j] = 0; } } } var str = ""; if (max == 0) { return ""; } else { for (var i = index - max; i <= max; ++i) { str += word1[i]; } return str; } 
}function lcsBruteForce(word1, word2) {var maxLength = 0;var longestSubstring = "";for (var i = 0; i < word1.length; i++) {for (var j = i + 1; j <= word1.length; j++) {var substring = word1.substring(i, j);if (word2.includes(substring) && substring.length > maxLength) {maxLength = substring.length;longestSubstring = substring;}}}return longestSubstring;
}function max(a, b) { return (a > b) ? a : b; 
} function knapsack(capacity, size, value, n) { if (n == 0 || capacity == 0) { return 0; } if (size[n - 1] > capacity) { return knapsack(capacity, size, value, n - 1); } else { return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1)); } 
} function dKnapsack(capacity, size, value, n) { var K = []; for (var i = 0; i <= capacity + 1; i++) { K[i] = []; } for (var i = 0; i <= n; i++) { for (var w = 0; w <= capacity; w++) { if (i == 0 || w == 0) { K[i][w] = 0; } else if (size[i - 1] <= w) { K[i][w] = max(value[i - 1] + K[i-1][w-size[i-1]], K[i-1][w]); } else { K[i][w] = K[i - 1][w]; } console.log(K[i][w] + " "); } } return K[n][capacity]; 
}function ksack(values, weights, capacity) { var load = 0; var i = 0; var w = 0; while (load < capacity && i < 4) { if (weights[i] <= (capacity-load)) { w += values[i]; load += weights[i]; } else { var r = (capacity-load)/weights[i]; w += r * values[i]; load += capacity-load; } ++i; } return w; 
} 
/* 
var items = ["A", "B", "C", "D"]; 
var values = [50, 140, 60, 60]; 
var weights = [5, 20, 10, 12]; 
var capacity = 30; 
console.log(ksack(values, weights, capacity));
*/function makeChange(origAmt, coins) { var remainAmt = 0; if (origAmt % .25 < origAmt) { coins[3] = parseInt(origAmt / .25); remainAmt = origAmt % .25; origAmt = remainAmt; } if (origAmt % .1 < origAmt) { coins[2] = parseInt(origAmt / .1); remainAmt = origAmt % .1; origAmt = remainAmt; } if (origAmt % .05 < origAmt) { coins[1] = parseInt(origAmt / .05); remainAmt = origAmt % .05; origAmt = remainAmt; } coins[0] = parseInt(origAmt / .01);
} function showChange(coins) { if (coins[3] > 0) { console.log("25 美分的数量 - " + coins[3] + " - " + coins[3] * .25); } if (coins[2] > 0) { console.log("10 美分的数量 - " + coins[2] + " - " + coins[2] * .10); } if (coins[1] > 0) { console.log("5 美分的数量 - " + coins[1] + " - " + coins[1] * .05); } if (coins[0] > 0) { console.log("1 美分的数量 - " + coins[0] + " - " + coins[0] * .01); } 
} var origAmt = .63; 
var coins = []; 
makeChange(origAmt, coins); 
showChange(coins);