1

Тема: Задачка

Загалом потрібна допомога з алгоритмом

Прихований текст

Кажуть, що у цю пору року на Алясці великим попитом
користуються холодильники українського виробництва. Зеник та
Марічка вирішили скористатися цим феноменом.
На ринку в Україні є N холодильників вітчизняного виробництва.
Зеник та Марічка знають за скільки гривень вони зможуть придбати
холодильник в Україні та за скільки гривень його можна продати на
Алясці. Кожен з холодильників можна придбати не більше ніж у
одному екземплярі.
Наші юні герої мають K гривень у своєму розпорядженні. Вони
хочуть придбати деякі з холодильників на своїй батьківщині (для
цього вони можуть витратити не більше ніж K гривень) та потім
продати їх на Алясці. Вам необхідно визначити максимально можливу
кількість грошей Зеника та Марічки після здійснення купівлі та
продажу. Вважатимемо, що транспортування холодильників є
безкоштовним. Зауважте, що Зеник та Марічка можуть поїхати
продавати холодильники на Аляску тільки один раз. Також вони
можуть при бажанні взагалі нічого не купувати та нічого не
продавати.

Вхідні дані:
Перший рядок містить через пробіл два цілих числа N та K.
Наступні N рядків містять через пробіл по два цілих числа Ai та Bi.
Тут Ai – ціна i-го холодильника в Україні, а Bi – на Алясці.

Вихідні дані:
Єдине ціле число – максимально можливий капітал Зеника та
Марічки після поїздки до Аляски.

приклад

Приклад вводу:
5 18
5 8
20 1000
18 25
12 17
7 4

Приклад виводу:
26

2

Re: Задачка

Q-bart написав:

Вам необхідно визначити максимально можливу
кількість грошей Зеника та Марічки після здійснення купівлі та
продажу.

Може,просто кількість грошей(що мається на увазі під МАКСИМАЛЬНИМ)? Дані ж вводяться 1 раз (під час одного виконання програми)?

3

Re: Задачка

КиївОболонь написав:
Q-bart написав:

Вам необхідно визначити максимально можливу
кількість грошей Зеника та Марічки після здійснення купівлі та
продажу.

Може,просто кількість грошей(що мається на увазі під МАКСИМАЛЬНИМ)? Дані ж вводяться 1 раз (під час одного виконання програми)?

Мається на увазі, знайти скільки максимально можуть заробити Зеник і Марічка, після того як куплять холодильники в україні, і продадуть на Алясці.

4

Re: Задачка

Для початку, напевно,треба помножити Н на Аі та Н на Ві. А потім відняти від К, те що множили(його ще додати треба)

5 Востаннє редагувалося Q-bart (18.11.2015 21:54:14)

Re: Задачка

КиївОболонь написав:

Для початку, напевно,треба помножити Н на Аі та Н на Ві. А потім відняти від К, те що множили(його ще додати треба)

Вартість кожного холдильника вже дана окремо (ai, bi).

6

Re: Задачка

Q-bart написав:
КиївОболонь написав:

Для початку, напевно,треба помножити Н на Аі та Н на Ві. А потім відняти від К, те що множили(його ще додати треба)

Вартість кожного холдильника вже дана окремо (ai, bi).

Тобто кожен холодильник має різну ціну?

7 Востаннє редагувалося koala (18.11.2015 23:08:18)

Re: Задачка

Сортуємо холодильники за вартістю в Україні.
Пишемо рекурсивну функцію, що повертає максимальний прибуток від масиву при заданій сумі грошей. Якщо за гроші можна купити всі - повертаємо прибуток від всіх (не забуваємо залишок). В іншому разі порівнюємо прибуток за умови купівлі чи некупівлі першого в масиві, обчислений нашою функцією від хвоста масиву.
Задача NP-повна, так що нічого не програєте.

десь так
def findMaxIncome( fridges, money ):
  if len(fridges)==0:
    return money
  if sum(fridge[0] for fridge in fridges)<money:
    return money+sum(fridge[1]-fridge[0] for fridge in fridges)
  if fridges[0][0] > money:
    return findMaxIncome(fridges[1:], money)
  return max(findMaxIncome(fridges[1:], money),findMaxIncome(fridges[1:], money-fridges[0][0]+fridges[0][1]))
Подякували: Q-bart1

8

Re: Задачка

koala написав:

Сортуємо холодильники за вартістю в Україні.
Пишемо рекурсивну функцію, що повертає максимальний прибуток від масиву при заданій сумі грошей. Якщо за гроші можна купити всі - повертаємо прибуток від всіх (не забуваємо залишок). В іншому разі порівнюємо прибуток за умови купівлі чи некупівлі першого в масиві, обчислений нашою функцією від хвоста масиву.
Задача NP-повна, так що нічого не програєте.

десь так
def findMaxIncome( fridges, money ):
  if len(fridges)==0:
    return money
  if sum(fridge[0] for fridge in fridges)<money:
    return money+sum(fridge[1]-fridge[0] for fridge in fridges)
  if fridges[0][0] > money:
    return findMaxIncome(fridges[1:], money)
  return max(findMaxIncome(fridges[1:], money),findMaxIncome(fridges[1:], money-fridges[0][0]+fridges[0][1]))

Як він буде вести себе на таких тестових даних?

Прихований текст

3 100
100 1000
1 5
2 10

9 Востаннє редагувалося Yola (19.11.2015 13:25:26)

Re: Задачка

Хіба це не задача про рюкзак?

Гадаю, вам потрібно розібратись з динамічним програмуванням.

Подякували: koala, Q-bart2