1 Востаннє редагувалося Q-bart (20.03.2015 15:48:19)

Тема: Перебір

І знову вітаю.
В мене проблемка, треба реалізувати функцію на перебір.

Завдання

Розробити функцію bouquets(narcissus_price, tulip_price, rose_price, summ),
яка приймає 4 аргументи -- додатні дійсні числа (ціни за один нарцис, тюльпан та троянду, і суму грошей у кишені головного героя),
та повертає ціле число -- кількість варіантів букетів, які можна скласти з цих видів квітів, таких щоб вартість кожного букету не перевищувала summ.

Не забути, що букети з парною (загальною) кількістю квітів живим дівчатам не дарують. Тести із некоректними даними не проводяться.

Я навіть уявити алгоритму не можу... Поясніть як можна зробити  такий перебір.
Допоможіть!

2 Востаннє редагувалося Chemist-i (20.03.2015 16:08:43)

Re: Перебір

Обираємо найдешевше (наприклад це тюльпани), і цілочислено ділимо сумм на ціну найдешеших квітів, отримуємо теоретичний максимум ітерації данного виду, а тепер в трьох вкладених цикла перебираємо ціну тієї або іншої квітки помножити на номер ітерації і зразу рахуємо, якщо вкладаємось - збільшуєм каунтер на одиницю, як ні - не збільшуємо. Результатом буде - каунтер. (Кантер спочатку знулити, в самому початку функції). Алгоритм дуже не оптимальний, проте перше, що в голову прийшло.

псевдо
КількістьНайдешевших = самм / мінімум(тюльпан_прайс, іншаквітка_прайс, третяквітка_прайс);

каунтер = 0;
цикл (і = від 1 до КількістьНайдешевших)
  цикл (j = від 1 до КількістьНайдешевших)
    цикл (k = від 1 до КількістьНайдешевших)
    {
      якщо (і*тюльпан_прайс + j*іншаквітка_прайс + k*третяквітка_прайс <= самм) то каунтер++;
    }

виводимо каунтер;
Подякували: Q-bart1

3 Востаннє редагувалося quez (20.03.2015 16:20:43)

Re: Перебір

Ех, а могли б прикинутись шлангом і запостити задачу в "Цікаві задачі", отримали б і алгоритм, і рішення. :D

Уточнення по умові: можна тратити не всі гроші? А то в мене boquet(1, 1, 1, 10) повертає 0, якщо треба потратити максимально можливу суму, то це навіть правильно.

4

Re: Перебір

quez написав:

Ех, а могли б прикинутись шлангом і запостити задачу в "Цікаві задачі", отримали б і алгоритм, і рішення. :D

Уточнення по умові: можна тратити не всі гроші? А то в мене boquet(1, 1, 1, 10) повертає 0, якщо треба потратити максимально можливу суму, то це навіть правильно.

гроші можуть лишитися

5

Re: Перебір

І ще одне: перестановки рахуються як один варіант?

Подякували: Chemist-i, leofun012

6

Re: Перебір

quez написав:

І ще одне: перестановки рахуються як один варіант?

Оцього я не врахував.

7 Востаннє редагувалося Q-bart (20.03.2015 17:23:23)

Re: Перебір

quez написав:

І ще одне: перестановки рахуються як один варіант?

Враховуються букети які містять різняться між собою різною кількістю квітів
тобто, нам всеодно в якому порядку увіти будуть в букеті, значення має лише кількість кожної із квіток у букеті

8 Востаннє редагувалося Q-bart (20.03.2015 16:48:20)

Re: Перебір

Chemist-i, ви ще неврахували те що парними к-сть квітів дарув не можна...  Та я це добавив..
Отже, що вийшло

def bouquets(narcissus_price, tulip_price, rose_price, summ):
    chepest = summ / min(narcissus_price, tulip_price, rose_price)
    print chepest
    counter = 0
    for i in range(1, chepest+1):
        for j in range(1, chepest+1):
            for k in range(1, chepest+1):
                if (i*narcissus_price + j * tulip_price + k*rose_price)>=summ and (i+j+k)% 2 != 0:
                    counter += 1
                    
    return counter
print bouquets(1,1,1,5) #має бути 34, рахує 62
print bouquets(2,3,4,10) # має бути 12, рахує 62
print bouquets(2,3,4,100) # має бути 4019, рахує 59524

Десь помилка..

9 Востаннє редагувалося P.Y. (20.03.2015 17:30:59)

Re: Перебір

Варіант для любителів ФП (ще не тестив)
[code=python]from itertools import *

def bouquets(narcissus_price, tulip_price, rose_price, summ):
    prices=[narcissus_price, tulip_price, rose_price]
    min_price=min(prices)
    return len(tuple(
        filter    (lambda price: price<=summ,
        map       (sum,
        chain(
        *map      (lambda n:combinations_with_replacement(prices, n),
        takewhile (lambda n: n*min_price<=summ,
        count(1, step=2))))))))[/code]

Подякували: Q-bart1

10 Востаннє редагувалося Q-bart (20.03.2015 17:25:37)

Re: Перебір

P.Y. написав:

Варіант для любителів ФП (ще не тестив)
[code=python]from itertools import *

def bouquets(narcissus_price, tulip_price, rose_price, summ):
    prices=[narcissus_price, tulip_price, rose_price]
    min_price=min(prices)
    return len(tuple(
        filter    (lambda price: price<=summ,
        map       (sum,
        chain(
        *map      (lambda n:combinations_with_replacement(prices, n)
        takewhile (lambda n: n*min_price<=summ,
        count(1, step=2))))))))[/code]

Помилка
   

takewhile (lambda n: n*min_price<=summ,
            ^
SyntaxError: invalid syntax

11

Re: Перебір

У попередньому рядку кому забув (уже виправив). Кажу ж, не тестив.

12

Re: Перебір

Q-bart написав:

def bouquets(narcissus_price, tulip_price, rose_price, summ):
    chepest = summ / min(narcissus_price, tulip_price, rose_price)
    print chepest
    counter = 0
    for i in range(1, chepest+1):
        for j in range(1, chepest+1):
            for k in range(1, chepest+1):
                if (i*narcissus_price + j * tulip_price + k*rose_price)>=summ and (i+j+k)% 2 != 0:
                    counter += 1
                    
    return counter
print bouquets(1,1,1,5) #має бути 34, рахує 62
print bouquets(2,3,4,10) # має бути 12, рахує 62
print bouquets(2,3,4,100) # має бути 4019, рахує 59524

Десь помилка..

  • Загальна сума витрат на квіти має бути менша за наявний бюджет, а в вас - більша: (i*narcissus_price + j * tulip_price + k*rose_price)>=summ

  • Кількість подарованих квітів повинна бути парна, тобто остача від ділення на 2 має дорівнювати нулю, а в вас - не дорівнює.

  • Можна враховувати що букет без якогось типу квітки - теж букет, тому не range(1, chepest+1), а  range(chepest+1)

Раджу роздруковувати в циклі комбінації що виходять, допомагає зневаджувати:

print '%3d)' % counter, '(narsicces={})*{} + (tulips={})*{} + (roses={})*{} = {} <= {}'.format(
    narcissus_price, i, tulip_price, j, rose_price, k, total, summ
)
Подякували: Q-bart1

13

Re: Перебір

Дякую!!!

bunyk написав:

Загальна сума витрат на квіти має бути менша за наявний бюджет, а в вас - більша: (i*narcissus_price + j * tulip_price + k*rose_price)>=summ

Точно, помилився..

bunyk написав:

Кількість подарованих квітів повинна бути парна, тобто остача від ділення на 2 має дорівнювати нулю, а в вас - не дорівнює.

А тут не погоджуюся...

Задача написав:

Не забути, що букети з парною (загальною) кількістю квітів живим дівчатам не дарують. Тести із некоректними даними не проводяться.

bunyk написав:

Можна враховувати що букет без якогось типу квітки - теж букет, тому не range(1, chepest+1), а  range(chepest+1)

Саме так.. пропустив..

14

Re: Перебір

Давайте по індукції. Якщо є тільки один вид квітів, то матимемо int(summ/price) варіантів (int - ціла частина), якщо вважати "букет" без квітів за варіант, і на один менше. якщо не вважати. Якщо є два види квітів, то якщо першого виду 0, то другого - до int(summ/price[2]), якщо першого 1, то другого до int((summ-price[1])/price[2]), якщо першого виду i, то другого до int((summ-i*price[1])/price[2]), максимум першого, очевидно, int(summ/price[1]), а всього - сума в циклі по i int((summ-i*price[1])/price[2]). Для третього і т.д. ніби вже очевидно - зовнішні цикли...

Подякували: Q-bart1

15

Re: Перебір

Q-bart написав:
bunyk написав:

Кількість подарованих квітів повинна бути парна, тобто остача від ділення на 2 має дорівнювати нулю, а в вас - не дорівнює.

А тут не погоджуюся...

Задача написав:

Не забути, що букети з парною (загальною) кількістю квітів живим дівчатам не дарують. Тести із некоректними даними не проводяться.

*FACEPALM* І це вже в мене не перший випадок. Добре що цього разу не з живою дівчиною помилився.

16

Re: Перебір

не з живою дівчиною помилився.

Хто про що подумав, а я про німецький анатомічний театр  Ґюнтера фон Хаґенза :)
http://www.funeralcommunity.com/sites/default/files/files/1/plastination-gunther-von-hagens-body-worlds-7.jpg

Подякували: leofun011

17

Re: Перебір

koala написав:

Давайте по індукції. Якщо є тільки один вид квітів, то матимемо int(summ/price) варіантів (int - ціла частина), якщо вважати "букет" без квітів за варіант, і на один менше. якщо не вважати. Якщо є два види квітів, то якщо першого виду 0, то другого - до int(summ/price[2]), якщо першого 1, то другого до int((summ-price[1])/price[2]), якщо першого виду i, то другого до int((summ-i*price[1])/price[2]), максимум першого, очевидно, int(summ/price[1]), а всього - сума в циклі по i int((summ-i*price[1])/price[2]). Для третього і т.д. ніби вже очевидно - зовнішні цикли...

Я таки не поняв... Шо означає один чи 2 чи 3  види квітів?

18 Востаннє редагувалося Q-bart (21.03.2015 13:55:40)

Re: Перебір

Написав такий код

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

def bouquets(narcissus_price, tulip_price, rose_price, summ):
    chepest = summ / min(narcissus_price, tulip_price, rose_price)
    
    counter = 0L
    for i in range(chepest+1):
        for j in range(chepest+1):
            for k in range(chepest+1):
                if (i*narcissus_price + j * tulip_price + k*rose_price)<=summ and (i+j+k)% 2 != 0:
                    counter += 1
                    
    return counter

Та занадто довго(>15 s.) працює з bouquets(200,300,400,100000)
Потім оптимізував до такого

Прихований текст
def bouquets(narcissus_price, tulip_price, rose_price, summ):

    counter = 0
    chepest = summ / min(narcissus_price, tulip_price, rose_price)
    
    for i in range(chepest+1):
        if i*narcissus_price<=summ:
            for j in range(chepest+1):
                if i*narcissus_price +j*tulip_price<=summ:
                    for k in range(chepest+1):
                        if ( i*narcissus_price + j * tulip_price + k*rose_price)<=summ and (i+j+k)% 2 != 0:
                            counter += 1
                    
    return counter

З "bouquets(200,300,400,100000) " працює 10 сек. Та превіряльник дальше пише що не вкладаюся в 15 сек., як можна його оптимізувати??

19 Востаннє редагувалося koala (21.03.2015 18:23:06)

Re: Перебір

На ideone не падає, хоча там на час обмеження важке: http://ideone.com/f4hjgZ
Внутрішній цикл не потрібен, бо там просте ділення. Сортування дозволяє крутити меншу кількість циклів.

А ще інтуїція підказує, що там буде формула без циклів, якщо кількість грошей кратна НСК цін на квіти, і можна зменшити sum на таке кратне. Але ліньки виводити.

Подякували: Q-bart1

20

Re: Перебір

Q-bart написав:

занадто довго(>15 s.) працює з bouquets(200,300,400,100000)

Мій варіант із цими параметрами до 2 хв. працює :(