javascript algorithm

knapsack.js

/*
 * 要求：0 1 背包问题
 * 参考：https://segmentfault.com/a/1190000012829866
 */
 
 function knapsack(weights, values, W) {
    /*
     * 根据公式计算填写表格 f(i, j)
     * i=0 && j<wi    f(i, j)=0
     * i=0 && j>=wi   f(i, j)=v0
     * i>0 && j<wi    f(i, j)=f(i, -1)
     * i>0 && j>=wi   f(i, j)=max(f(i-1, j), vi+f(i-1, j-wi)) 
     * 表格最后一个即为最优解
     */
    var n = weights.length -1
    var f = [[]]
    for (var j = 0; j <= W; j++) {
        if (j < weights[0]) {
           f[0][j] = 0
        } else {
           f[0][j] = values[0]
        }
    }
    for (var j = 0; j <= W; j++) {
        for (var i = 1; i <= n; i++ ) {
            if (!f[i]) {
                f[i] = []
            }
            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]) 
            }
        }
    }
    
   /*
    * 逆推求解最优解的构成
    * 只要当前行不等于上一行的总价值，就能挑出第i件物品，然后j减去该物品的重量，一直找到j = 0就行了
    */
   var selected = []
   var j = W
   for (var i=n; i>=0; i--) {
       if (j === 0) break
       if (i===0) {
           selected.push(0)
       } else if (f[i][j] > f[i-1][j]) {
           selected.push(i)
           j = j - weights[i];
       }
    }
    return selected.reverse()
}
console.log('result', knapsack([2,2,6,5,4], [6,3,5,4,6], 10))

quickSort.js

/*
 * 要求：快速排序
 * 参考：https://mp.weixin.qq.com/s/PQLC7qFjb74kt6PdExP8mw
 */
function quickSort(arr) {
  qsort(arr, 0, arr.length - 1)
}

function qsort(arr, left, right){
  if (left >= right) return

  let pivotIndex = partition(arr, left, right)
  qsort(arr, left, pivotIndex - 1)
  qsort(arr, pivotIndex + 1, right)
}

function partition(arr, left, right) {
  let pivotIndex = Math.floor((right + left) / 2)
  let pivot = arr[pivotIndex]

  while(left < right) {
    // 必须先从有开始
    while(right > left && arr[right] > pivot) {
      right--
    }

    while(left < right && arr[left] <= pivot) {
      left++
    }

    if (left < right) {
      let temp = arr[left]
      arr[left] = arr[right]
      arr[right] = temp
      left++
      right--
    }
  }

  arr[pivotIndex] = arr[left]
  arr[left] = pivot
  return left
}

var arr = [1, 5, 3, 2, 7, 6, 10, 9]
quickSort(arr)