JavaScript Challenge - The Knapsack Problem

This community-built FAQ covers the “The Knapsack Problem” code challenge in JavaScript. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the JavaScript challenge The Knapsack Problem

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in #get-help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to #get-help and #community:tips-and-resources. If you are wanting feedback or inspiration for a project, check out #project.

Looking for motivation to keep learning? Join our wider discussions in #community

Learn more about how to use this guide.

Found a bug? Report it online, or post in #community:Codecademy-Bug-Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

So my code ended up a little differently from the psuedocode in the Knapsack Problem article (it didn’t exactly make sense to me…). I’m curious about others’ thoughts on this:

function knapsack(weightCap, weights, values) {
  // Write your code here
  const itemCt = weights.length;
  const matrix = new Array(itemCt);

  for (let row = 0; row <= itemCt; row++) {
    matrix[row] = new Array(weightCap + 1).fill(0);

    if (row > 0) {
      for (let col = 1; col <= weightCap; col++) {
        matrix[row][col] = Math.max(matrix[row - 1][col], matrix[row][col]);
        
        if (col === weights[row - 1]) {
          matrix[row][col] = Math.max(matrix[row][col], values[row - 1]);
        }
        
        if (col + weights[row - 1] <= weightCap && matrix[row - 1][col] > 0) {
          matrix[row][col + weights[row - 1]] = Math.max(matrix[row][col + weights[row - 1]], matrix[row - 1][col] + values[row - 1]);
        }
      }
    }
  }

  console.log(matrix);
  return Math.max(...matrix[itemCt]);
};

// Use this to test your function:
const weightCap = 10;
const weights = [3, 6, 8, 1, 3];
const val = [50, 60, 100, 200, 70];
console.log(knapsack(weightCap, weights, val));

// Leave this so we can test your code:
module.exports = knapsack;

I used an array of booleans to keep track of which of the items (the indices) I “stole”.
I created a function to see what next additional item I could “steal” given an array of booleans representing what I’d already “stolen”; (creating more arrays of booleans to keep track of those new possible sets of things I could “steal”).
And I used a different function (recursively) to either add one possibility of things I could “steal” to the list of possibilities for a set I can choose to “steal”, or call the function to check if I could “steal” more.

Afterward, I iterated through my list (array) of possibilities, and checked which of then had the highest value; and returned that value.

My solution is not efficient because it produces the same possibility more than one … since it generates the possibility in every possible order of what can be “stolen”. (Meaning it creates permutations, but combinations are all that is needed).

function getMore(weightCap, weights, used) {
  const length = weights.length;
  // if every item is used (used is all true) then return null;
  if (used.every(value => value)) {
    return null;
  }
  const additional = []; // additional possibilities
  let weight = 0;
  for (let i = 0; i < length; i++) {
    if (used[i]) {
      weight += weights[i];
    }
  }
  for (let j = 0; j < length; j++) {
    if (!used[j]) {
      if (weight + weights[j] <= weightCap) {
        let another = used.slice();
        another[j] = true;
        additional.push(another);
      }
    }
  }
  // if no possibilities to add, then return null
  if (additional.length == 0) {
    return null;
  }
  return additional;
}

function knapsack(weightCap, weights, values) {
  const possibilities = [];
  const length = weights.length;
  let used = new Array(length);
  used.fill(false);

  function getPossibilities(weightCap, weights, used) {
    let more = getMore(weightCap, weights, used);
    if (more == null) { 
      possibilities.push(used);
    }
    else {
      for (let boolArrays of more) {
        getPossibilities(weightCap, weights, boolArrays);
      }
    }
  }

  getPossibilities(weightCap, weights, used);
  let max = 0;
  let best = used;
  let i = 0;
  for (let possibility of possibilities) {
    let value = 0;
    let weight = 0;
    for (let j = 0; j < length; j++) {
      if (possibility[j]) {
        value += values[j];
        weight += weights[j];
      }
    }
    if ((value > max) && (weight <= weightCap)) {
      max = value;
      best = possibility;
    }
    i++;
  }
  return max;
};

My solution took a while but here it is


function knapsack(weightCap, weights, values) {

  // Write your code here
  let high = 0;
  
  for(let i = 0; i < weights.length; i++){
    let cap = weights[i];//3
    let val = values[i]; //70
    let newCap = weights[i]; //3
    let newVal = values[i];
    for(let j = i + 1; j < weights.length; j++){
      if(cap < weightCap && cap + weights[j] <= weightCap){
        cap += weights[j];
        val += values[j];
      }else if(newCap + weights[j] <= weightCap){
        cap = newCap + weights[j];
        val = newVal + values[j];
      }
      if(val > high){
        high = val;
      }
    }
  }

  return high;
};

// Use this to test your function:
const weightCap = 10;
const weights = [3, 6, 3];
const val = [70, 60, 100];
console.log(knapsack(weightCap, weights, val));

module.exports = knapsack;

//knapsack(weightCap, weights, val)

This is horribly long and convoluted. . . but it does work . . . pretty new to JS and this was my first try at this problem!

function knapsack(weightCap, weights, values) {
  // Write your code here
  let maxVal = 0;
  let weightHolder = 0;
  let valHolder = 0;

  const helperSum = (a, b) => {
  return a + b;
}
  for (let i=0; i<values.length; i++) {
    let a = weights[i]
    for (let j=0; j<values.length; j++) {
      if (i === j){
        continue;
      }
      let b = weights[j]
      if (helperSum(a, b) <= weightCap) {
        weightHolder = helperSum(a, b);
        valHolder = helperSum(values[i], values[j])
        for (let x=0; x<values.length; x++) {
          if (x === j || x == i) {
            continue;
          }
          if (helperSum(weightHolder, weights[x]) <= weightCap) {
            weightHolder = helperSum(weightHolder, weights[x]);
            valHolder += values[x];
          }
        } if (valHolder > maxVal) {
          maxVal = valHolder
        }
        
      } else if (values[i] > maxVal) {
          maxVal = values[i]
      }
    }
  } return maxVal;
};




// Use this to test your function:
const weightCap = 10;
const weights = [3, 6, 8];
const val = [50, 60, 100];
console.log(knapsack(weightCap, weights, val));

// Leave this so we can test your code:
module.exports = knapsack;```
function knapsack(weightCap, weights, values) {
    const list = weights
        .map((w, i) => ({w, i, v: values[i], p: (w / values[i])}))
        .sort((a, b) => a.p - b.p)
    let remainW = 10
    let result = 0
    list.forEach(({w, i, v, p}) => {
        if (w <= remainW) {
            result += v
            remainW -= w
        }
    })
    console.log(list)
    return result
};

Output

110

[ { w: 3, i: 0, v: 50, p: 0.06 }, { w: 8, i: 2, v: 100, p: 0.08 }, { w: 6, i: 1, v: 60, p: 0.1 } ] 

2/5 tests passed.

function knapsack(weightCap, weights, values) {
    let result = 0
    const sortValuable = (a, b) => b.v - a.v
    const list = weights.map((w, i) => ({w, i, v: values[i]})).sort(sortValuable)
    const getMaxValuable = (items, item) => {
        let remainW = weightCap - item.w
        let sum = item.v
        for (let otherItem of items.sort(sortValuable)) {
            if (otherItem.i === item.i) continue;
            if (remainW <= 0) break;
            if (otherItem.w <= remainW) {
                sum += otherItem.v
                remainW -= otherItem.w
            }
        }
        return sum
    }
    list.forEach(item => {
        item.sum = getMaxValuable(list, item)
    })
    return list.sort((a, b) => b.sum - a.sum)[0].sum
};

// Use this to test your function:
const weightCap = 10;
const weights = [3, 6, 8];
const val = [50, 60, 100];
console.log(knapsack(weightCap, weights, val));

test pass complete

Honestly shocked this worked lol

const knapsack = (weightCap, weights, values) => { const matrix = values // 1) Map values and weights to 2D Array [[value, weight], ...] // 2) Filter out any items with weight above cap // 3) Sort highest value to lowest .map((value, idx) => [value, weights[idx]]) .filter(item => item[1] <= weightCap) .sort((a, b) => b[0] - a[0]) let bagValue = 0; let bagWeight = 0; let itemIdx = 0; while(bagWeight < weightCap && itemIdx <= matrix.length - 1){ let itemValue = matrix[itemIdx][0]; let itemWeight = matrix[itemIdx][1]; if(bagWeight + itemWeight <= weightCap){ bagValue += itemValue; bagWeight += itemWeight; } itemIdx ++; } return bagValue; }; // Use this to test your function: const weightCap = 10; const weights = [3, 7, 6, 8]; const val = [50, 60, 60, 100]; console.log(knapsack(weightCap, weights, val)); // Leave this so we can test your code: module.exports = knapsack;
function knapsack(weightCap, weights, values) {
  let maxValue = 0;
  function next(num, weight, value) {
    for (let i = num; i < weights.length; i++) {
      if (weight + weights[i] <= weightCap) {
        next(i+1, weight + weights[i], value + values[i]);
      }
    }
    if (value > maxValue) {
      maxValue = value;
    }
  }
  next(0, 0, 0);
  return maxValue;
};