iframe-proxy | Sunbelt Computer Software

83 lines (72 loc) · 2.14 KB

 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 * Time and Space Complexity: O(n*cap)
const zeroOneKnapsack = (arr, n, cap, cache) => {
  // Base Case: No capacity or no items
  if (cap === 0 || n === 0) {
    cache[n][cap] = 0
    return cache[n][cap]
  // Lookup (value already calculated)
  if (cache[n][cap] !== -1) {
    return cache[n][cap]
  // Profit when excluding the nth item
  let notPick = zeroOneKnapsack(arr, n - 1, cap, cache)
  // Profit when including the nth item
  let pick = 0
  if (arr[n - 1][0] <= cap) {
    // If weight of the nth item is within the capacity
      arr[n - 1][1] + zeroOneKnapsack(arr, n - 1, cap - arr[n - 1][0], cache)
  cache[n][cap] = Math.max(pick, notPick) // maximize profit
  return cache[n][cap]
const example = () => {
  Problem Statement:
  You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
  You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.
  Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
  let input = `1
  input = input.trim().split('\n')
  input.shift()
  const length = input.length
  const output = []
  let i = 0
  while (i < length) {
    const cap = Number(input[i].trim().split(' ')[0])
    const currlen = Number(input[i].trim().split(' ')[1])
    let j = i + 1
    const arr = []
    while (j <= i + currlen) {
      arr.push(input[j])
    const newArr = arr.map((e) => e.trim().split(' ').map(Number))
    const cache = []
    for (let i = 0; i <= currlen; i++) {
      const temp = []
      for (let j = 0; j <= cap; j++) {
        temp.push(-1)
      cache.push(temp)
    const result = zeroOneKnapsack(newArr, currlen, cap, cache)
    output.push(result)
    i += currlen + 1
  return output
export { zeroOneKnapsack, example }

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

Uh oh!

FilesExpand file tree

ZeroOneKnapsack.js

Latest commit

History

ZeroOneKnapsack.js

File metadata and controls