| Bytes | Lang | Time | Link |
|---|---|---|---|
| 124 | Ruby | 160217T234926Z | PellMell |
| 274 | Python3 | 241019T153951Z | Ajax1234 |
| 036 | MATL | 160218T153257Z | Luis Men |
| 020 | Jelly | 160218T000550Z | Dennis |
| 025 | Pyth | 160217T203649Z | PurkkaKo |
Ruby, 124 bytes
->(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)
}
This is a brute-force solution.
Python3, 274 bytes
def f(l,t):
q,s,b=[([],t)],[],[]
for T,t in q:
if[]==[1 for i in t if sum(T)+i<=l]:b+=[(sum(T),T)]
for i,a in enumerate(t):
if(U:=sum(V:=T+[a]))<=l and(S:=sorted(V))not in s and all(U<o for o,_ in b):q+=[(V,t[:i]+t[i+1:])];s+=[S]
return min(b,key=lambda x:x[0])[0]
MATL, 36 bytes
iTFinZ^!"2G@2#)sXKt1G>~wb+lG>A*?KhX<
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
Jelly, 20 bytes
³œ-;⁴Ṃ;¹S>⁴
ŒPÇÐfS€Ṃ
TIO is fast enough to finish the last test cases within its 60 second time limit, even if just barely.
Background
The algorithm is both simple and inefficient:
We generate all subsets of T, counting multiplicities.
We filter the the subsets, keeping only those those subsets S that satisfy one of the following criteria:
S is different from T, and the sum of the elements of S and the minimal element not in S is larger than L.
S and T are identical.
The filtered T (let's call it T') now contains all lists of task that do just enough work (or even some overtime).
Of all S in T', pick the one with the lowest sum.
How it works
Œ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 bytes
JEhSsMf&gJsT>hS.-QT-JsTyQ
I haven't been able to run the last two test cases (they time out online, I assume), but all the others work. This is just a basic brute force solution.