Jump to content
Gecko

Algo Challenge

Recommended Posts

Se da un set/array/vector S ce cuprinde N valori reale, in ordine aleatorie, unde 0 < N <= 100,000. Fiecare valoare din set reprezinta valoarea unei monezi. Se cere realizarea unei solutii care poate gasi una dintre cele mai optime combinatii de monezi, in functie de valoarea acestora din set, care se aproprie cel mai mult de una sau multe valori date, V. De asemenea se va returna si totalul combinatiei gasite.

 

Precizari:

- Daca solutia este rulata de mai multe ori pe acelasi set de date cu alte valori date, trebuie sa ignore valorile monezilor pe care le-a folosit deja din set.

- Daca nu exista combinatii pentru a ajunge la valoarea dorita, se va returna un set gol.

 

Exemple:

 

N = 4

S = [70, 90, 45, 10]

V = 115

 

Rezultatul asteptat este [[70, 45], 115], intrucat 70 + 45 = 115

 

---

 

N = 4

S = [70, 90, 32, 10]

V = 115

 

Rezultatul asteptat este [[70, 32, 10], 112], intrucat 70 + 32 + 10 = 112, care reprezinta cea mai apropriata combinatie de 115.

 

V = 40

 

Rezultatul asteptat este [[], 0], intrucat din set s-au eliminat valorile 70, 32 si 10, in pasul anterior, iar valoarea ramasa, 90, este mai mare decat 40.

 

---

 

Pentru stabilirea celor ce vor rezolva challenge-ul, va trebui sa-mi trimiteti solutia prin PM, intr-un limbaj rulabil in CLI (py/php ar fi perfect), pe care o voi rula si cronometra pe aceleasi seturi de date. Rezultatele trebuie sa fie asemanatoare cu urmatoarele:

 

N = 52

S = Set 52

V = 50 | Rezultat: [[30.84, 19.12], 49.96]

V = 40 | Rezultat: [[31.49, 8.12], 39.61]

V = 30 | Rezultat: [[29.66], 29.66]

 

Timp de executie: 40ms

 

---

 

N = 1,000

S = Set 1,000

V = 100 | Rezultat: [[33.79, 33.75, 32.46], 100.0]

V = 28 | Rezultat: [[14.14, 13.86], 28.0]

V = 7 | Rezultat: [[3.88, 3.12], 7.0]

 

Timp de executie: 70ms

---

 

N = 100,000

S = Set 100,000

V = 127.93 | Rezultat: [[42.65, 42.65, 42.63], 127.93]

V = 88.92 | Rezultat: [[44.46, 44.46], 88.92]

V = 14.85 | Rezultat: [[14.85], 14.85]

 

Timp de executie: 1.7s

 

---


Voi posta solutia mea la final, cea cu care am generat timpii de mai sus.

 

---

 

Lista celor care au rezolvat pana acum:

-

-

-

-

-

  • Thanks 1
  • Upvote 3

Share this post


Link to post
Share on other sites

Avem voie sa folosim (intern) un vector sortat? Adica sa il sortam. Pe el sau o copie a lui.

Cand zici "cea mai apropriata combinatie" te referi chiar daca suma e mai mare sau doar daca e mai mica? Intreb deoarece pe undeva mentionezi "Daca nu exista combinatii pentru a ajunge la valoarea dorita, se va returna un set gol"...

Edited by u0m3
  • Like 2

Share this post


Link to post
Share on other sites
10 hours ago, u0m3 said:

Avem voie sa folosim (intern) un vector sortat? Adica sa il sortam. Pe el sau o copie a lui.

Cand zici "cea mai apropriata combinatie" te referi chiar daca suma e mai mare sau doar daca e mai mica? Intreb deoarece pe undeva mentionezi "Daca nu exista combinatii pentru a ajunge la valoarea dorita, se va returna un set gol"...

Nu sunt limitari de ce puteti face, deci da, puteti sorta datele cum doriti.

 

Prin "cea mai apropriata combinatie" voiam sa spun mai mica sau egala cu valoarea data. Daca in set nu exista combinatii egale cu valoarea data, se accepta setul care se aproprie cel mai mic de valoare, dar care nu o depaseste.

  • Upvote 1

Share this post


Link to post
Share on other sites

Avand in vedere ca nu a rezolvat nimeni pana acum, am sa postez solutia, insa challenge-ul ramane un exercitiu bun pentru oricine. Challenge-ul este inspirat dintr-o situatie reala pe care am intalnit-o la un proiect la care lucrez acum.

 

Am comentat fiecare linie pentru a putea urmari firul si cei ce nu au experiente cu Python. Daca inca aveti nelamuriri, va astept cu intrebari.

 

#!/usr/bin/env python3

import sys
import math
import random

if len(sys.argv) < 3:
    print('You need to specify the values and number of generated items')
    print('e.g.: ./pick.py 50,40,30 1000')
    sys.exit(0)

debug = len(sys.argv) > 3
iterations = 0
available_items = []
no_of_generated_items = int(sys.argv[2])

for i in range(0, no_of_generated_items):
    available_items.append(random.randint(122, 4999) / 100)

if debug:
    with open('items.txt', 'w') as items_fh:
        items_fh.write(str(available_items))
        items_fh.close()

# Sort the items in reverse order.
available_items.sort(reverse = True)

# Remove an item from the available items.
def forget_items (items):
    for item in items:
        try:
            index = available_items.index(item)
            del available_items[index]
        except ValueError:
            pass

# Magic happens.
def solution (desired_value):
    global iterations

    # Stores the combinations that add up to the desired_value.
    possibilities = {}

    # Stores the combination that's closest to the desired_value.
    current_max = { 'items': [], 'total': 0 }

    # Iterate through all of the available items.
    for value in available_items:
        # Ignore all the values bigger than the desired_value because they're useless.
        if value > desired_value:
            continue

        if debug: iterations += 1

        # Initialize a place in the possibilities list for the current value if necessary.
        if not value in possibilities:
            possibilities[value] = { 'total': 0, 'items': [] }

        # Iterate through the current possibilities.
        for k, possibility in possibilities.items():
            if debug: iterations += 1

            # Add the current item's value and the item itself to the total
            # of each possibility if it's not larger than the desired_value.
            if possibility['total'] + value <= desired_value:
                possibility['total'] += value
                possibility['items'].append(value)

                # If this possibility's total just became the desired_value,
                # return prematurely with the combination.
                if possibility['total'] == desired_value:
                    forget_items(possibility['items'])

                    return possibility
                # Otherwise, check the new total against the current total.
                elif possibility['total'] > current_max['total']:
                    # Store the new total.
                    current_max = possibility.copy()

    if current_max['total'] == 0:
        return { 'items': [], 'total': 0 }

    forget_items(current_max['items'])

    return current_max

for value in sys.argv[1].split(','):
    print(solution(float(value)))

if debug:
    print('Iterations', iterations)

 

Pentru a o rula, o copiati intr-un fisier .py, si executati astfel:

 

python pick.py 50,40 1000

 

Daca mai adaugati un parametru o sa intre in debug mode si o sa printeze numarul de iteratii si o sa scrie valorile generate automat in items.txt.

 

python pick.py 50,40 1000 y

 

  • Upvote 5

Share this post


Link to post
Share on other sites
On 11/28/2018 at 12:03 PM, Gecko said:

Se da un set/array/vector S ce cuprinde N valori reale, in ordine aleatorie, unde 0 < N <= 100,000. Fiecare valoare din set reprezinta valoarea unei monezi. Se cere realizarea unei solutii care poate gasi una dintre cele mai optime combinatii de monezi, in functie de valoarea acestora din set, care se aproprie cel mai mult de una sau multe valori date, V.

Nu e problema rucsacului ? 

https://ro.wikipedia.org/wiki/Problema_rucsacului

Share this post


Link to post
Share on other sites

Era sa uit, am mai avut o versiune inainte de cea mai sus care era eficienta ca timp de executie doar pana la 500 items. Pentru cei ce nu au multa experienta cu algoritmica, ca mine, am sa-l pun si pe asta pentru ca presupun ca unii dintre voi asa ati inceput sa ganditi problema si poate se dovedeste util pentru a observa unde ati gresit, prin comparatie cu solutia de mai sus. Ambele fac acelasi lucru, dar solutia de mai sus e mai bine optimizata.

 

def get_items_for_amount (amount, ignored_values = []):
    global iterations

    total = 0
    items = []

    for value in available_items:
        if value in ignored_values:
            continue

        iterations += 1

        if total + value <= amount:
            total += value
            items.append(value)

            if total == amount:
                forget_items(items)

                return items, total

    ignore_values = []
    unique_values = list(set(available_items))
    
    unique_values.sort(reverse = True)

    if not len(ignored_values):
        for value in unique_values:
            ignore_values.append(value)

            new_items, new_total = get_items_for_amount(amount, ignore_values)

            if new_total > total:
                total = new_total
                items = new_items

        forget_items(items)

    return items, total

 

  • Thanks 1

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...