Solving the algorithm question using javascript

Question

I don't know how to think about a question. Since I know the people here are much more experienced and guiding, I would like to ask you. I'd appreciate it if you could solve the problem and explain it. Question:

"Think that you have an unlimited number of carrots, but limited number of carrot types. Also, you have one bag that can hold a limited weight. Each type of carrot has a weight and a price. Write a function that takes carrotTypes and capacity and return the maximum value the bag can hold."

I'm not sure I fully understand the question and understand how I can do it. I'd be very happy if you could help me.

let carrotTypes = [{
    price: 100,
    kg: 2
  },
  {
    price: 120,
    kg: 4
  },
  {
    price: 80,
    kg: 7
  }
];

let bagCapacity = 36; //kg

getMaxValue(carrotTypes, bagCapacity)

function getMaxValue(carrotTypes, capacity) {

  carrotTypes.forEach(carrot => {
     console.log(carrot);
  });

}

It seems to me it's yet another variation of the Knapsack problem, perhaps this could help you: https://stackoverflow.com/questions/7774769/how-do-i-solve-the-classic-knapsack-algorithm-recursively, — FlatAssembler, May 30 '20 at 13:33
you have a classic [Knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem). — Nina Scholz, May 30 '20 at 13:33
@questioner sorry, i not understanding your question,do you can explain again for me — linthertoss, May 30 '20 at 14:27

score 0 · Accepted Answer · answered May 30 '20 at 14:42

You could take a brute force method and get all possible vcombinations and return the one with the smallest total.

The result is a bag which the count of items of the same index of the given data.

function getMaxValue(data, target) {
    function iter(index, bag, weight, total) {
        if (weight > target) return;
        if (weight === target) {
            if (!result || total < result.total) result = { bag, weight, total };
            return;
        }
        let temp = [...bag];
        temp[index]++;
        iter(index, temp, weight + data[index].kg, total + data[index].price);
        if (++index >= data.length) return;
        iter(index, bag, weight, total);
    }

    var result;
    iter(0, data.map(_ => 0), 0, 0);
    return result;
}

let carrotTypes = [{ price: 100, kg: 2 }, { price: 120, kg: 4 }, { price: 80, kg: 7 }],
    bagCapacity = 36,
    bag = getMaxValue(carrotTypes, bagCapacity);

console.log(bag);

.as-console-wrapper { max-height: 100% !important; top: 0; }

score 0 · Answer 2 · answered May 30 '20 at 15:51

I would suggest building your thinking like this. Start breaking the problem in smaller parts. What if your bag is able to hold 2kg weight?

For better understanding, I am modifying the values. So let's suppose you have 3 carrot types

 let carrotTypes = [{
    price: 50,
    kg: 1
  },
  {
    price: 100,
    kg: 2
  },
  {
    price: 80,
    kg: 3
  }
];

Random small numbers so that you can get a feel of it and your bag can hold is 3Kg.

Now proceed to this problem, assuming max weight bag can handle is 0 what will be the answer then, and then increase the maximum weight one by one. Also, what if you have only 1 type of carrot, and then increase the types of carrot.

Max Weight Bag can handle

             0       1       2        3
(50)  1      0       50     100     150
(100) 2      0       50     100     150
(80)  3      0       50     100     150

Either you can choose to select that carrot type or not. So if you choose to select(only if you can i.e., CarrotTypeWeight < WeightBag can hold)

CarrotTypePrice + Answer(WeightBag can hold - CarrotTypeWeight) -> moving left in the table

If you choose not to select

Answer(WeightBag can hold when you don't have this type) -> moving up in the table

I hope you can visualize it. Last number matrix[n-1][n-1] will be your answer.

Solving the algorithm question using javascript

2 Answers2