算法
背包问题 - 找出背包中装了哪些东西
const knapsack = (weights:number[], values:number[], total:number) => {
var n = weights.length;
var f = [[]];
f[-1] = new Array(total+1).fill(0);
for(var i=0; i<n; i++){
f[i] = new Array(total).fill(0);
for(var j=0; j<=total; j++){
if(j < weights[i]){
f[i][j] = f[i-1][j];
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]);
}
}
}
console.log(f)
var totalWeight = 0,
j = total;
for(var i=n;i--;){
if(f[i][j] > f[i-1][j]){
console.log(`选择物品：${i}；重量为：${weights[i]}；价值为：${values[i]}`);
totalWeight += weights[i];
j -= weights[i];
}
}
console.log(`背包最大承重：${total}；实际重量：${totalWeight}；最大价值：${f[n-1][total-1]}`)
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],14)
背包问题递归解法
var selectMap = {};
const knapsack = (weights:number[], values:number[], total:number, w?:number) => {
if(w === undefined){
w = weights.length - 1;
}
if(total === 0 || w < 0){
return 0
}
var lastData = knapsack(weights, values, total, w - 1);
if(total < weights[w]){
return lastData;
}
var newData = knapsack(weights, values, total - weights[w], w - 1) + values[w];
if(lastData < newData){
selectMap[w] = true;
return newData;
}else{
selectMap[w] = false;
return lastData;
}
}
var ws = [2,2,6,5,4];
var vs = [6,3,5,4,6];
var ts = 16;
var totalWeight = 0;
var a = knapsack(ws,vs,ts);
console.log(selectMap)
Object.keys(selectMap).map(i => {
if(selectMap[i]){
totalWeight += ws[i];
console.log(`选择物品：${i}；重量为：${ws[i]}；价值为：${vs[i]}`);
}
});
console.log(`背包最大承重：${ts}；实际重量：${totalWeight}；最大价值：${a}`)
背包问题-可装同样物件
const knapsack = (weights:number[], values:number[], total:number) => {
var n = weights.length;
var f = [[]];
f[-1] = new Array(total+1).fill(0);
for(var i=0; i<n; i++){
f[i] = new Array(total).fill(0);
for(var j=0; j<=total; j++){
if(j < weights[i]){
f[i][j] = f[i-1][j];
}else{
for(var k = 0; k*weights[i] <= j; k++){
f[i][j] = Math.max(f[i-1][j], f[i-1][j-k * weights[i]] + values[i] * k);
}
}
}
}
var totalWeight = 0,
j = total;
for(var i=n;i--;){
if(f[i][j] > f[i-1][j]){
var k = 0;
while(f[i][j] > f[i-1][j]){
k++;
j -= weights[i];
}
totalWeight += weights[i] * k;
console.log(`选择物品：${k} 个 ${i}；重量为：${weights[i] * k}；价值为：${values[i] * k}`);
}
}
console.log(`背包最大承重：${total}；实际重量：${totalWeight}；最大价值：${f[n-1][total]}`)
}
knapsack([2, 3, 4, 7], [1, 3, 5, 9], 10)
多重背包问题 - 每个物品最多个 n 个
const knapsack = (weights:number[], values:number[], numbers:number[], total:number) => {
var n = weights.length;
var f = [[]];
f[-1] = new Array(total+1).fill(0);
for(var i=0; i<n; i++){
f[i] = new Array(total).fill(0);
for(var j=0; j<=total; j++){
if(j < weights[i]){
f[i][j] = f[i-1][j];
}else{
for(var k = 1; k*weights[i] <= j && k<= numbers[i]; k++){
f[i][j] = Math.max(f[i-1][j], f[i-1][j-k * weights[i]] + values[i] * k);
}
}
}
}
var totalWeight = 0,
j = total;
for(var i=n;i--;){
if(f[i][j] > f[i-1][j]){
var k = 0;
while(f[i][j] - f[i-1][j - weights[i]] === values[i] && k < numbers[i]){
k++;
j -= weights[i];
}
totalWeight += weights[i] * k;
console.log(`选择物品：${k} 个 ${i}；重量为：${weights[i] * k}；价值为：${values[i] * k}`);
}
}
console.log(`背包最大承重：${total}；实际重量：${totalWeight}；最大价值：${f[n-1][total]}`)
}
knapsack([2,3,1],[2,3,4],[1,4,1],6)
知识整理
内存
以下讨论的内存模型为 node V8 的内存模型
内存管理模型
- 代码区：存放即将执行的代码片段
- 栈：存放局部变量
- 堆：存放对象、闭包上下文
- 堆外内存：不通过 V8 分配，也不受 V8 管理的内存，Buffer 对象的数据就存放于此。
代码区内存回收
这部分内存几乎不回收，存储的大部分是 AST，代码通过解释器引擎解析出来的结果。
栈区内存回收
栈（Stack）的分配与回收非常直接，当程序离开某作用域后，其栈指针下移（回退），整个作用域的局部变量都会出栈，内存收回。
堆外内存回收
堆外内存由系统管理，内存回收也只收到系统级别的调度。
堆内存回收
堆区内存结构
首先 V8 引擎内存由两部分组成：新生代、老年代。
新生代：年轻的新对象，未经历垃圾回收或仅经历过一次
老年代：存活时间长的老对象，经历过一次或更多次垃圾回收的对象
两个不同的内存结构回收机制也不同，大小也不同，老年代大约是新生代的 40 倍左右。
新生代垃圾回收
新生代由于大部分的对象是短时间存在的，所以在 GC 时大部分的对象都会是被删除，少部分是存活的，所以在新生代采用的是复制算法，这样的话性能会更好，但是对空间的利用率更低，因为需要拿出一部分来作为复制。
Scavenge 算法将新生代的总空间一分为二，只使用其中一个，另一个处于闲置，等待垃圾回收时使用。使用中的那块空间称为 From，闲置的空间称为 To。
垃圾回收开始时 From 空间所有应该存活的对象都复制完成后，原本的 From 空间将被释放，成为闲置空间，原本 To 空间则成为使用中空间，两个空间进行角色翻转。
新生代内存晋升老年代
对象一开始进来的时候都会先进入新生代，但是由于内存有限，所有的对象不可能一直存活在新生代，所以会有对象从新生代晋升到老年代的过程。
-
对象此前已经经历过一次新生代垃圾回收，这次依旧应该存活，则晋升至老年代。
-
To空间已经使用了25%，则将此对象直接晋升至老年代。
标记清除
顾名思义，标记-清除算法分为两个阶段，标记(mark)和清除(sweep)
老年代的内存回收为标记清除，想要了解老年代的回收内存，首先就会先想到如何标记哪些是会需要回收的，哪些是不需要的。
标记的方案是从根节点开始向下遍历，js 是基于原型链的，根对象就那么几个（BOM，DOM，CSSOM）是一个深度遍历的过程，所有被引用的对象存在引用关系的就是活着的对象，这个时候会记录为可达对象，就是能访问到的对象。
这个时候会对堆内存从头到尾进行线性的遍历，如果发现对象没有被标识为可达对象，就会将其回收。下图就是一个堆内存区被标记并且清除过后的内存现状，呈碎片化。
标记整理
上述的标记清除之后会留下一堆不连续的内存段，这些内存段不完整意味着如果有大的对象过来，发现每个小格子都放不下，但是他们把空格子合并起来是可以放下的，这就会造成空间浪费。
那就又想到一种方法，标记整理，将实体的对象都合并起来，然后放到一起，重新整理内存，合并地址，然后将大的内存块腾出来，使空间变得紧凑重新让空间利用起来。
但是标记整理会非常耗费时间，并且在整理的过程中必须是所有的运行都会停下来，等整理完成之后才会恢复，所以标记整理发生的时机就变成了，当有大对象进来已经放不下的时候。下图是整理之后的结果
增量标记
上述的方案能完成整个垃圾回收了，但是标记清楚是需要全停顿的，所以一旦进行 GC 的时候，浏览器就卡住了，在我们的视觉上，60 fps 左右的帧频是最接受的，所以我们采取了增量标记的方案，如果触发 GC，那我们会把每个整个 GC 分成多个步骤，每执行一个步骤，停歇一下，把内存还给浏览器，执行完浏览器的操作，GC 再进行下一个步骤。这样交替执行就提高了程序流畅性，一定程度上避免了长时间的卡顿。
内存泄露
前端的内存泄露的情况会一般发生引用计数。这也是垃圾回收的机制。但是引用计数只是标记的阶段。
引用计数是指一个值的引用次数是 0，就表示这个值将不再用到，因此可以将这块内存释放。
内存泄露发生于这个值不再需要了，但是引用计数却不为 0，垃圾回收机制并不能回收这块内存，从而导致内存泄露。
比如说 DOM：如果一个 js 对象对一个 DOM 持有引用，删除了 DOM，但是这个时候 js 对 DOM 有引用，所以 DOM 的引用计数是 1，所以内存并不会将 DOM 进行回收。
var element = document.getElementById('button');
function onClick(event) {
element.innerHtml = 'text';
}
element.addEventListener('click', onClick);
element.removeEventListener('click', onClick);
element.parentNode.removeChild(element);
下面是几个常见的内存泄露实例：
function foo(arg) {
bar = "this is a hidden global variable";
}
理论上讲弹栈之后，内存就会被回收的，但是由于 bar 变成了全局对象，此时内存并不会回收 bar，如果不手动清除，bar 就永远不会清除了
var someResource = getData();
setInterval(function() {
var node = document.getElementById('Node');
if(node) {
node.innerHTML = JSON.stringify(someResource));
}
}, 1000);
当 node DOM 节点被删掉了，但是 setInterval 会不断的执行，但是处理程序一直处于活跃，所以并不能回收 someResource 也会导致内存泄露。
var theThing = null;
var replaceThing = function () {
var originalThing = theThing;
var unused = function () {
if (originalThing)
console.log("hi");
};
theThing = {
longStr: new Array(1000000).join('*'),
someMethod: function () {
console.log(someMessage);
}
};
};
setInterval(replaceThing, 1000);
闭包对于环境变量的持有，由于 unused 和 someMethod 共享了闭包上下文环境，所以两者没有都被标记为不用时，一直不会回收
作用域
词法作用域 or 动态作用域
js 是词法作用域，就是说解释器引擎在解释 js 的时候，就已经确定作用域了，从下面的例子可以看出来：
function foo(){
// js 会输出 2
// 如果输出的是 3 就是动态作用域如 bash
console.log(a);
}
function bar(){
let a = 3;
foo();
}
let a = 2;
bar()
什么是作用域
作用域一般在前端指的是当前代码执行的上下文环境，这句话比较抽象，下面介绍几个概念。
- VO：变量对象
- AO：活动对象
- this：当前环境的 this 指向
- scope：指向父级作用域
变量对象可以理解为当函数还没有执行的时候，由于 js 有声明提前的概念，所以会有 VO 对象的概念，申请内存的时候先方进去，AO 是当代码执行的时候，就会将属于当前作用域的 VO 变为 AO。
this 是在函数执行的时候确定的。下周详细说一下 this
作用域类型
作用域大致分为：函数作用，全局作用域，块级作用域。
函数作用域：也称局部作用域，在函数大括号之间的内容就是该函数的作用域。
全局作用域：js 会有根对象，这个根对象提供一些除了语法之外的 API 让 js 的代码来调用，这个对象所处的环境就是全局作用域，比如 window。
块级作用域：js 是没有块级作用域的，并且有声明提前的概念，所以没有办法在 if 内声明一个变量。
作用域链
当函数内部想要使用一个变量时，这个时候会从当前作用域中寻到变量，如果不存在该变量，会到上一个作用域中寻找，所以变量间是有关系的，这个关系类似于 js 的原型链。子指向父的关系。小的作用域中的 scope 指向父级执行上下文。
这样作用域一层一层的关系就形成了作用域链，也就形成了变量逐级向上查找的关系，如果没有找到就会报一个错 变量is not defined
实例
var x = 10;
function foo() {
var y = 20;
function bar() {
var z = 30;
alert(x + y + z);
}
bar();
}
foo(); // 60
// 全局上下文的变量对象是
globalContext.VO === Global = {
x: 10
foo: <reference to function>
};
// 在“foo”创建时，“foo”的[[scope]]属性是
foo.[[Scope]] = [
globalContext.VO
];
// 在“foo”激活时（进入上下文），“foo”上下文的活动对象是
fooContext.AO = {
y: 20,
bar: <reference to function>
};
// “foo”上下文的作用域链为：
fooContext.Scope = fooContext.AO + foo.[[Scope]] // i.e.:
fooContext.Scope = [
fooContext.AO,
globalContext.VO
];
// 内部函数“bar”创建时，其[[scope]]为：
bar.[[Scope]] = [
fooContext.AO,
globalContext.VO
];
// 在“bar”激活时，“bar”上下文的活动对象为：
barContext.AO = {
z: 30
};
// “bar”上下文的作用域链为：
barContext.Scope = barContext.AO + bar.[[Scope]] // i.e.:
barContext.Scope = [
barContext.AO,
fooContext.AO,
globalContext.VO
];
// 对“x”、“y”、“z”的标识符解析如下：
- "x"
-- barContext.AO // not found
-- fooContext.AO // not found
-- globalContext.VO // found - 10
- "y"
-- barContext.AO // not found
-- fooContext.AO // found - 20
- "z"
-- barContext.AO // found - 30
this
js 是词法作用域，这个前一章已经大概介绍了，这个是作用域的概念，this 是在函数被调用时发生的绑定，this 可以理解成作用域的一部分，它的指向完全取决于函数在哪里调用的。
this 的四种绑定规则
既然 this 是在函数执行的时候才会被绑定，那么就有它的绑定规则，下面介绍四种绑定规则。
默认绑定
const foo = () => {
console.log(this.a) // 输出 a
}
var a = 2; // 变量声明到全局对象中
foo();
默认绑定我们可以看做隐式绑定的一种特殊情况，实际上是 window.foo()， 所以我们可以理解成被绑定到全局对象中，如果是在浏览器中，就会被绑定到全局对象中。
隐式绑定
const foo = () => {
console.log(this.a);
}
let obj1 = {
a: 1,
foo
};
let obj2 = {
a: 2,
foo
}
obj1.foo(); // 输出 1
obj2.foo(); // 输出 2
遵循函数谁是调用者，this 就会指向谁。所以这里的 this 调用方就是两个 obj。
显式绑定
- call(this, arg1, arg2, …)
- apply(this, [arg1, arg2, …])
- bind(this, arg1, arg2)
前两个是在执行的时候指定 this 的指向。bind 是永久性将 this 指向到某个对象上。内部实现也是用 call 或者 apply 实现的。
new 绑定
js 没有类的概念，实现类和继承都是基于原型链的，代码实现就是构造函数。实例化的时候会使用 new 来得到一个实例。实际上是 return 了当前构造函数的 this。
class Foo{
construtor(){
return this;
}
}
var foo = new Foo();
foo 拿到了构造函数的 this 的引用，就可以根据 this + 原型链 调用 Foo 的构造函数的方法和原型链上的方法了。
优先级
new > 显式绑定 > 隐式绑定 > 默认绑定
闭包
在 js 中闭包可以理解为环境变量的引用。由于 js 的函数执行是用栈进行存储的，所以出栈时，相关函数的环境变量，都会被回收。如果有一些异步操作想要使用该环境变量中的部分变量。就需要使用闭包了。
变量引用不全是闭包
const foo = () => {
var a = 1;
const getA = () => {
console.log(a);
}
}
上述的情况也使用到了外层的环境变量，但是我们并不认为这种情况是闭包。因为在 foo 出栈的时候，a 和 getA 都是内部的环境变量，这个时候外部没有对这两个变量进行持有，都会被回收掉。
真正意义上的闭包
const foo = () => {
var a = 1;
const getA = () => {
console.log(a);
}
return getA;
}
var fooA = foo();
现在 foo 方法将一个函数返回给了 fooA，所以外部变量对 getA 有了引用，此时 getA 内部的函数调用持有 foo 的环境变量 a 的引用。所以 foo 执行完毕之后，依旧不会释放掉内部的环境变量。
就算我们执行完 fooA() 也不会释放掉 foo 的环境变量。只有当 fooA = null 的时候，getA 发现自己没有被引用了，下一次 gc 的时候才会回收。
闭包优化
上面的流程可以看出来，闭包有好处，可以引用到环境变量，这里用到的词是引用，不是复制，两者会有差别，复制只是多了一个变量，引用将整个环境变量持有。
基于这样就在现有的闭包机制下，优化了环境变量的持有。
function outer () {
var x; // 真正的局部变量
var y; // context variable, 被inner1使用
var z; // context variable, 被inner2使用
function inner1 () {
use(y);
}
function inner2 () {
use(z);
}
function inner3 () {
/* 虽然函数体为空，但是作为闭包，依旧引用outer的Context */
}
return [inner1, inner2, inner3];
}
上述的情况的话，x 是不会被放到闭包的环境变量中的，也就是说真正被引用到的环境变量才会放入一个闭包的机制中。
上述的情况当 inner1 执行完毕之后，也不会立刻释放 y，inner2 也不会立刻释放 z，(y,z,content) 会被一起当做一个闭包变量保存着。
即使 inner3 并没有引用任何变量，但其实是引用了 content 这样的环境变量。
所以只有当 inner1, inner2, inner3 都不再被引用时。才会释放掉这个段闭包。
闭包嵌套
所以，性能上就不要发生闭包嵌套了。这更是一种性能无法忍受的问题