tło

Wyobraź sobie przez chwilę, że masz nudną i nudną pracę. Każdego ranka dostajesz zestaw zadań, które powinieneś wykonać tego dnia. Każde zadanie ma określony czas trwania i po uruchomieniu musi zostać wykonane za jednym razem. Twój szef nie będzie tolerował pracy na biegu jałowym, więc jeśli są jeszcze zadania, które możesz wykonać przed powrotem do domu, musisz popracować nad jednym z nich (możesz wybrać, który z nich). I odwrotnie, jeśli wszystkie pozostałe zadania wymagałyby pracy w godzinach nadliczbowych, musisz wrócić do domu wcześniej! Dlatego Twoim celem jest zminimalizowanie długości dnia roboczego poprzez sprytne planowanie.

Ciekawostka: jest to jeden z wariantów leniwego biurokratycznego problemu planowania i jest trudny do rozwiązania ( źródło ).

Wejście

Masz dwa dane wejściowe: liczbę „jednostek czasu” w dniu roboczym (dodatnia liczba całkowita L) oraz zbiór zadań (niepusta tablica dodatnich liczb całkowitych Treprezentujących czas trwania zadania). Można je pobierać w dowolnej kolejności i w dowolnym rozsądnym formacie. Tablica Tmoże zawierać zadania o czasie trwania dłuższym niż L, ale z pewnością zawiera co najmniej jedno zadanie o czasie trwania L.

Wynik

Poprawny harmonogram jest podzbiorem zadania S ⊆ Ttakie, że sum(S) ≤ L, i każde zadanie nie w S(krotności liczenia) ma długość ponad surowo L - sum(S). Twój wynik będzie najmniejszą możliwą sumą prawidłowego harmonogramu. Innymi słowy, podasz minimalną liczbę jednostek czasu, które musisz dziś pracować.

Przykład

Rozważ dane wejściowe

L = 9
T = [3,4,4,4,2,5]

Jednym ze sposobów planowania dnia jest [4,4]: ukończenie dwóch zadań w 8 jednostkach czasu i pozostanie 1 jednostka. Ponieważ żadne zadania jednoczęściowe nie są dostępne, możesz wrócić do domu. Jednak harmonogram [2,5]jest jeszcze lepszy: pracujesz przez 7 jednostek czasu, a następnie wszystkie pozostałe zadania zajęłyby 3 lub więcej jednostek czasu. Harmonogram [2,4]nie jest prawidłowy, ponieważ po przepracowaniu 6 jednostek czasu nadal będziesz mieć wystarczająco dużo czasu, aby ukończyć zadanie 3 jednostek. 7 jednostek okazuje się optymalnych, więc poprawna wydajność to 7.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma ograniczeń czasowych, więc brutalne zmuszanie jest całkowicie dopuszczalne.

Przypadki testowe

Są one podane w formacie L T -> output.

 1 [1,2] -> 1
 6 [4,1] -> 5
 7 [7,7,9] -> 7
 9 [3,4,4,4,2,5] -> 7
20 [6,2,3,12,7,31] -> 17
42 [7,7,7,7,8,8,8] -> 36
42 [7,7,7,7,7,8,8,8] -> 35
42 [7,7,7,7,7,7,8,8,8] -> 36
16 [1,2,3,4,5,6,7,8,9,10] -> 13
37 [15,27,4,1,19,16,20,26,29,18] -> 23
22 [24,20,8,8,29,16,5,5,16,18,4,9] -> 18
80 [10,22,11,2,28,20,27,6,24,9,10,6,27,2,15,29,27] -> 71
59 [26,28,5,4,7,23,5,1,9,3,7,15,4,23,7,19,16,25,26] -> 52

Galaretka, 20 bajtów

³œ-;⁴Ṃ;¹S>⁴
ŒPÇÐfS€Ṃ

Wypróbuj online!

TIO jest wystarczająco szybki, aby zakończyć ostatnie przypadki testowe w terminie 60 sekund, nawet jeśli ledwo.

tło

Algorytm jest zarówno prosty, jak i nieefektywny:

1. Generujemy wszystkie podzbiory T , licząc krotności.

2. Filtrujemy podzestawy, zachowując tylko te podzbiory S, które spełniają jedno z następujących kryteriów:

   • S różni się od T , a suma składników S i minimalnym elementu nie w S jest większy niż L .

   • S i T są identyczne.

   Filtrowany T (nazwijmy go T ' ) zawiera teraz wszystkie listy zadań, które wykonują wystarczającą ilość pracy (lub nawet nadgodziny).

3. Ze wszystkich S w T ' wybierz ten o najniższej sumie.

Jak to działa

ŒPÇÐfS€Ṃ     Main link. Left input: T (list). Right input: L (integer).

ŒP           Powerset; generate all subsets of T.
   Ðf        Filter them...
  Ç            applying the helper link.
     S€      Compute the sum of each kept subset.
       Ṃ     Take the minimum.

³œ-;⁴Ṃ;¹S>⁴  Helper link. Input: A (subset of T)

³œ-          Multiset subtraction; remove the elements of A from T, counting
             multiplicities.
   ;⁴        Append L to the resulting list.
     Ṃ       Take the minimum.
             If S == T, the difference was empty and the minimum is L.
      ;¹     Prepend the minimum to A.
        S    Compute the sum.
         >⁴  Compare it with L.
             If S == T, the comparison will return 1.

Pyth, 26 25 bajtów

JEhSsMf&gJsT>hS.-QT-JsTyQ

Wypróbuj online. Zestaw testowy.

Nie udało mi się uruchomić dwóch ostatnich przypadków testowych (zakładam, że upłynęły limity czasu online), ale wszystkie pozostałe działają. To tylko podstawowe rozwiązanie brutalnej siły.

Rubin, 124 bajty

->(m,s){
f=proc{|l,t|t.reject!{|x|x>l}
(0...(t.size)).map{|x|
f.call(l-t[x],t[0,x]+t[(x+1)..-1])
}.max||l
}
m-f.call(m,s)
}

To rozwiązanie brutalnej siły.

MATL , 36 bajtów

iTFinZ^!"2G@2#)sXKt1G>~wb+lG>A*?KhX<

Wypróbuj online!

i           % input number L
TF          % array [true, false]
in          % input array T. Get its length
Z^!         % Cartesian power and transpose. Each column is a selection from T
"           % for each selection
  2G@2#)    %   take non-selected and then selected tasks
  sXK       %   sum of selected tasks. Copy to clipboard K
  t1G>~     %   duplicate. Is sum of selected tasks <= L?
  wb        %   swap, rotate
  +         %   sum of selected tasks plus each non-selected task
  lG>A      %   are all of those numbers greater than L?
  *         %   are both conditions met?
  ?         %   if so
    Kh      %     paste current minimum (or initially L), append new value
    X<      %     compute new minimum
            %   end if implicitly
            % end for each implicitly
            % display stack implicitly