Hejto.pl
Hejto
/Wpisy
/Dyskusja
EXCV31
EXCV31
Kompan
w Programowanie

Cześć.


Potrzebowałbym wsparcia technicznego/informacji, na temat tego jakiego algorytmu muszę użyć.


Cel: Program który po wprowadzeniu kilku/nastu tasków wraz z poziomem trudności od 1 do 5 podzieli te taski tak, aby ich sumaryczny czas wynosił 8.00h.


Przykład:


Task1, trudność 1


Task2, trudność 1


Task3, trudność 1


Task4, trudność 1


Task5, trudność 5


Oczekiwane działanie:


Task1: Zajął 1h


Task2: Zajął 1h


Task3: Zajął 1h


Task4: Zajął 1h


Task5: Zajął 4h


SUMA: 8.00h


Oczywiście poziomy trudności mogą być inne, a program miałby sam określić ile dana rzecz zajęła, mając na uwadze że taski z wyższą trudnością musiały zająć proporcjonalnie większą ilość czasu.


Chciałbym to zaimplementować w języku Python, wraz z przyszłym wrzucaniem tego z automatu przez API do Jira.


Ma ktoś pomysł jak się za to zabrać? ChatGPT rozkłada ręce.


#pytanie #programowanie #informatyka #algorytmy

Komentarze (7)

panek
panek

Łączny czas / suma trudności i masz ile zajmuje jedna jednostka pracy. Żadnego fancy algorytmu nie trzeba o ile zakładamy że trudność i czas są liniowo powiązane

cec
cec

Patrzcie jaki zwyrodnialec - story pointy na godziny chce przeliczać ( ͡° ͜ʖ ͡°)

A może po prostu od razu wyceniać w jednostkach czasu? Albo przyjąć 1 punkt trudności = 1 godzina?

  1. Sumujesz wszystkie trudności z wszystkich tasków.

  2. Obliczasz współczynnik godzin na stopień trudności (chyba nie muszę pisać jakie działanie tutaj zastosować?).

  3. Mnożysz stopień trudności przez współczynnik i masz wynik w godzinach ¯\_(ツ)_/¯

shiranai
shiranai

Wygląda mi to na typowy problem plecakowy lub któryś z jego wariantów:


Jeśli poziom trudności zawsze jest tak samo przeliczany na czas (np. trudność 1 zawsze oznacza 1 godzinę), to można go zignorować i od razu mówić o czasie. Czyli twój problem brzmi: "mam X kontenerów o pojemności Y (tutaj: 8h), do którego mam wrzucić przedmioty różnej wielkości (tutaj: o różnym czasie trwania) tak, aby maksymalnie zapełnić kontenery".


Ja osobiście bym zrobił prosty, zachłanny algorytm "wpakuj największy pasujący task aż zabraknie miejsca", ale skoro planujesz użyć Pythona, to na pewno znajdziesz miliard bibliotek z lepszymi algorytmami.

Knapsack problem

Knapsack problem

The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. The name "knapsack problem" dates back to the early works of the mathematician Tobias Dantzig (1884–1956), and refers to the commonplace problem of packing the most valuable or useful items without overloading the luggage...

Wikipedia
sierzant_armii_12_malp
sierzant_armii_12_malp

@EXCV31 Eeee… nie rozumiem. Chodzi o problem plecakowy, czy jak?

sierzant_armii_12_malp
sierzant_armii_12_malp

@EXCV31 https://en.wikipedia.org/wiki/Subset_sum_problem ? Przepraszam, ale nie do końca rozumiem problem. Co to dokładnie znaczy „podzieli te taski tak, aby ich sumaryczny czas wynosił 8.00h”? Jak rozdzielę monety o łącznej wartości 100 zł pomiędzy iluś ludzi, to ich łączna wartość dalej będzie wynosiła 100 zł.

Subset sum problem

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S {\displaystyle S} of integers and a target-sum T {\displaystyle T} , and the question is to decide whether any subset of the integers sum to precisely ...

Wikipedia
nest0r171
nest0r171

def knapsack(tasks, difficulty_levels):

n = len(tasks)<br />

dp = [[0] * (n + 1) for _ in range(9)]  # Tablica przechowująca wyniki<br />


# Obliczanie optymalnego rozwiązania<br />

for i in range(1, n + 1):<br />

    task_time = tasks[i - 1]<br />

    difficulty = difficulty_levels[i - 1]<br />

    for j in range(1, 9):<br />

        if difficulty <= j:<br />

            dp[j][i] = max(dp[j][i - 1], dp[j - difficulty][i - 1] + task_time)<br />

        else:<br />

            dp[j][i] = dp[j][i - 1]<br />


# Odtworzenie rozwiązania<br />

selected_tasks = []<br />

j = 8<br />

for i in range(n, 0, -1):<br />

    if dp[j][i] != dp[j][i - 1]:<br />

        selected_tasks.append(i)<br />

        j -= difficulty_levels[i - 1]<br />


return selected_tasks<br />

Przykładowe dane

tasks = [1, 1, 1, 1, 4]

difficulty_levels = [1, 1, 1, 1, 5]


selected_tasks = knapsack(tasks, difficulty_levels)

total_time = sum(tasks[i - 1] for i in selected_tasks)


Wyświetlenie wyniku

for task_index in selected_tasks:

print(f"Task{task_index}: Zajął {tasks[task_index - 1]}h")<br />

print(f"\nSUMA: {total_time:.2f}h")

Zaloguj się aby komentować