раницаСветлина

Намерихте два предмета в сандък със съкровище! Първият артикул тежи weight1 и струва value1, а вторият артикул тежи weight2 и струва value2. Каква е общата максимална стойност на артикулите, които можете да вземете със себе си, ако приемем, че максималното ви тегло е maxW и не можете да се върнете за артикулите по-късно?

Имайте предвид, че има само два артикула и не можете да носите повече от един артикул от всеки тип, т.е. не можете да вземете два първи артикула или два втори артикула.

Пример

  • За value1 = 10, weight1 = 5, value2 = 6, weight2 = 4 и maxW = 8 изходът трябва да бъде
    knapsackLight(value1, weight1, value2, weight2, maxW) = 10.
    Можете да носите само първия елемент.
  • За value1 = 10, weight1 = 5, value2 = 6, weight2 = 4 и maxW = 9 резултатът трябва да бъде
    knapsackLight(value1, weight1, value2, weight2, maxW) = 16.
    Вие сте достатъчно силни, за да вземете и двата елемента със себе си.
  • За value1 = 5, weight1 = 3, value2 = 7, weight2 = 4 и maxW = 6 резултатът трябва да бъде
    knapsackLight(value1, weight1, value2, weight2, maxW) = 7.
    Не можете да вземете и двата елемента, но можете да вземете който и да е от тях.

Вход/Изход

  • [времево ограничение за изпълнение] 4 секунди (js)
  • [input] integer value1
    Гарантирани ограничения:
    2 ≤ value1 ≤ 20.
  • [въведено] цяло число тегло1
    Гарантирани ограничения:
    2 ≤ weight1 ≤ 10.
  • [input] integer value2
    Гарантирани ограничения:
    2 ≤ value2 ≤ 20.
  • [въведено] цяло число тегло2
    Гарантирани ограничения:
    2 ≤ weight2 ≤ 10.
  • [input] integer maxW
    Гарантирани ограничения:
    1 ≤ maxW ≤ 20.
  • [изход] цяло число

За това решение се опитах първо да обработя най-широките случаи, така че всяка стъпка във функцията да се тревожи за по-малко условия.

Първото условие, което проверявам, е случаят, когато maxW е по-малко от двете стойности.

function knapsackLight(value1, weight1, value2, weight2, maxW) {
  if (maxW < weight1 && maxW < weight2) return 0;
}

Следващото условие, което проверих, беше дали maxW ще ни позволи да носим и двата обекта.
if (maxW >= weight1 + weight2) return value1 + value2;

След това знаем, че само едно тегло е по-малко или равно на maxW. Трябва да проверим дали и двете тегла са по-малки от maxW и ако е така да изберем това с по-висока стойност.

if (maxW >= weight1 && maxW >= weight2) {
  return value1 > value2 ? value1 : value2;
}

Не на последно място, ние сме в състояние, в което само един предмет е в нашите възможности за носене. За да разберете кое можем да вземем, изберете произволно тегло и вижте дали е по-малко от maxW, дали стойността на обектите е връщане. Ако не върнете другия.
return maxW >= weight1 ? value1 : value2;

Ето пълния алгоритъм.

function knapsackLight(value1, weight1, value2, weight2, maxW) {
  if (maxW < weight1 && maxW < weight2) return 0;
  
  if (maxW >= weight1 + weight2) return value1 + value2;
  
  if (maxW >= weight1 && maxW >= weight2) {
    return value1 > value2 ? value1 : value2;
  }
  return maxW >= weight1 ? value1 : value2;
}

Публикувайте вашите решения в коментарите!