Решение вопроса об алгоритме с использованием javascript

Question

Я не знаю, как думать о вопросе. Поскольку я знаю, что люди здесь гораздо более опытные и руководящие, я хотел бы спросить вас. Буду признателен, если вы сможете решить проблему и объяснить ее. Вопрос:

«Подумайте, что у вас есть неограниченное количество моркови, но ограниченное количество видов моркови. Кроме того, у вас есть одна сумка, которая может выдержать ограниченный вес. Каждый тип моркови имеет свой вес и цена. Напишите функцию, которая принимает carrotTypes и capacity и возвращает максимальное значение, которое может вместить сумка. "

Я не уверен, что полностью понимаю вопрос и понимаю, как я могу это сделать. Я был бы очень рад, если бы вы мне помогли.

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);
  });

}

Answer 1

Я бы посоветовал строить ваше мышление вот так. Начните разбивать проблему на более мелкие части. Что делать, если ваша сумка выдерживает вес 2 кг?

Для лучшего понимания я изменяю значения. Итак, предположим, что у вас есть 3 типа моркови

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

Случайные маленькие числа, чтобы вы могли почувствовать это, и ваша сумка может вместить 3 кг.

Теперь приступим к этой задаче, предполагая Максимальный вес, который может выдержать сумка, равен 0, каков будет ответ, а затем увеличивайте максимальный вес один за другим. Кроме того, что, если у вас есть только 1 тип моркови, а затем увеличьте количество видов моркови. не. Итак, если вы решите выбрать (только если вы можете, например, CarrotTypeWeight

CarrotTypePrice + Answer (WeightBag может удерживать - CarrotTypeWeight) -> перемещение влево в таблице

Если вы выберите не выбирать

Ответ (WeightBag может удерживать, если у вас нет этого типа) -> перемещение вверх по таблице

Надеюсь, вы сможете это визуализировать. Матрица последних чисел [n-1] [n-1] будет вашим ответом.

Answer 2

Вы можете взять метод грубой силы и получить все возможные комбинации v и вернуть тот, у которого наименьшее общее количество.

Результатом является мешок, в котором количество элементов с одинаковым индексом данных.

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; }