14
\$\begingroup\$

The input for the continuous knapsack problem is as follows.

For each item 1...n we are given a positive weight and profit. Overall we are also given a positive capacity which is the maximum weight we can carry.

The goal is to pick items so that the profit is maximized without exceeding the capacity. This is hard if you can only pick either 1 or 0 of each item. But in the continuous version we are allowed to pick a fraction of an item as well.

A simple solution is to compute \$d_i = p_i/w_i\$ for each item \$i\$ (\$w_i\$ is the weight and \$p_i\$ is the profit for item \$i\$). We can then sort the \$d_i\$ from largest to smallest, picking each item from biggest to smallest while the capacity has not been reached and possibly a fraction of the final item which is chosen. This take \$O(n\log n)\$ time because of the sorting step.

Examples

Capacity 20

Profit Weight
9 6
11 5
13 9
15 7

Optimal profit 37.89.

For the optimal solution in this case we have chosen items with profits 11, 15 and 9 to start with. These have total weight 18 and profit 35. We now have 20-2 = 2 left before we reach weight capacity and the only remaining items has weight 9. So we take 2/9 of that item which gives us 2/9 of the profit 13. 35+(2/9)*13 = 37.8888....

If you increase the capacity to 50, say, then the optimal profit is 9+11+13+15 = 48.

Capacity 879

Profit Weight
91 84
72 83
90 43
46 4
55 44
8 6
35 82
75 92
61 25
15 83
77 56
40 18
63 58
75 14
29 48
75 70
17 96
78 32
40 68
44 92

The optimal profit is 1036.93.

Here is a larger example:

Capacity 995

Profit Weight
94 485
506 326
416 248
992 421
649 322
237 795
457 43
815 845
446 955
422 252
791 9
359 901
667 122
598 94
7 738
544 574
334 715
766 882
994 367
893 984
633 299
131 433
428 682
700 72
617 874
874 138
720 856
419 145
794 995
196 529
997 199
116 277
908 97
539 719
707 242
569 107
537 122
931 70
726 98
487 600
772 645
513 267
81 972
943 895
58 213
303 748
764 487
536 923
724 29
789 674
479 540
142 554
339 467
641 46
196 710
494 553
66 191
824 724
208 730
711 988
800 90
314 340
289 549
401 196
466 865
689 678
833 570
225 936
244 722
849 651
113 123
379 431
361 508
65 585
486 853
686 642
286 992
889 725
24 286
491 812
891 859
90 663
181 88
214 179
17 187
472 619
418 261
419 846
356 192
682 261
306 514
201 886
385 530
952 849
500 294
194 799
737 391
324 330
992 298
224 790

The optimal profit in this example is 9279.65.

Challenge

You can take the input in any form you like although please make it as easy as possible for me to test. Your code must output the optimal profit correct to within +- 0.01.

Most importantly, your code must run in linear time. This means you cannot use sorting to solve the problem. Your code can be either worst case linear or expected running linear.

However, this is still a challenge, so the shortest submission in bytes per language wins, but the complexity is restricted to linear.

\$\endgroup\$
7
  • \$\begingroup\$ I would suggest add some more small testcases. Also, maybe include some testcases where knapsack have enough complicity and may contain all elements. \$\endgroup\$
    – tsh
    Jun 23 at 8:41
  • \$\begingroup\$ Suggest testcases (in [[p1, w1], [p2, w2]], C -> OUT format): [[100,1]], 2 -> 100, [[100,10], [200,20], [100,20]], 2 -> 20, [[100,10],[200,20],[300,30]], 45 -> 450, [[100, 10], [100, 20], [100, 50]], 45 -> 230 \$\endgroup\$
    – tsh
    Jun 23 at 8:53
  • 2
    \$\begingroup\$ related cs.stackexchange.com post cs.stackexchange.com/questions/11620/… \$\endgroup\$
    – Bedstorm
    Jun 23 at 12:13
  • 2
    \$\begingroup\$ Because c is variable, that'd be \$O(nc^2)\$ = \$O(n^3)\$, not \$O(n)\$ \$\endgroup\$ Jun 24 at 10:24
  • 3
    \$\begingroup\$ @Jakque Stackmeter is right. That wouldn't have the right complexity. \$\endgroup\$
    – felipa
    Jun 24 at 10:45
6
\$\begingroup\$

Python 3, 332 \$\cdots\$ 242 252 bytes

from random import*
def f(l,W):
 a,b=choice(l);L=*M,=*S,=[]
 for p,w in l:[[M,S][p/w<a/b],L][p/w>a/b]+=(p,w),
 N,X=map(sum,zip(*L+[(0,0)]));A=X
 while X<W and M:*M,(p,w)=M;X+=w;N+=p
 return A>W and f(L,W)or X<W and N+(S>[]and f(S,W-X))or(W-X+w)*p/w+N-p

Try it online!

Runs in \$O(n)\$ time and space complexity.

Inputs a list of price and weight tuples along with the maximum capacity.
Returns the optimal profit.

Saved 3 bytes thanks to Jakque!!!
Saved 6 bytes thanks to pxeger!!!
Saved 8 bytes thanks to ovs!!!
Added 10 bytes to fix a bug kindly pointed out by Anush.

\$\endgroup\$
8
  • \$\begingroup\$ L=[];M=[];S=[]=> L=*M,=*S,=[] for -2 bytes and p,w=M.pop() => *M,(p,w)=M for -1 byte \$\endgroup\$
    – Jakque
    Jun 24 at 9:00
  • \$\begingroup\$ @Jakque Those are some very good golfs - thanks! :D \$\endgroup\$
    – Noodle9
    Jun 24 at 11:52
  • \$\begingroup\$ L=*M,=*S,=[] -> L=M=S=() and t=[(p,w)] -> t=(p,w), since you no longer mutate any of them. Also, a,b=choice(l)¶ X=N=0;L=*M,=*S,=[] -> a,b=choice(l);X=N=0;L=*M,=*S,=[] (where is a literal newline) \$\endgroup\$
    – pxeger
    Jun 24 at 15:08
  • \$\begingroup\$ @pxeger Super golfs - thanks! :D And thanks for pointing out the newline+space vs semicolon golf - was miscounting that! \$\endgroup\$
    – Noodle9
    Jun 24 at 15:25
  • 1
    \$\begingroup\$ @Anush Fixed - thanks! :D \$\endgroup\$
    – Noodle9
    Jun 25 at 11:00
5
\$\begingroup\$

Python3, 271 bytes

Runs in expected linear time. Essentially quickselect.

from random import *
def k(c,p,V=0):
    while p[1:]!=[]:
        i=randrange(len(p))
        m,l,r=(p[i][0]/p[i][1],i),[],[]
        for j,t in enumerate(p):
            [r,l][(t[0]/t[1],j)>=m]+=[t]
        v,w=map(sum,zip(*l))
        c,V,p=[(c,V,l),(c-w,V+v,r)][w<=c]
    v,w=(p+[(0,1)])[0]
    return V+v*min(c/w,1)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ could you add a TIO link? \$\endgroup\$
    – Anush
    Jun 24 at 4:23
  • \$\begingroup\$ A few more simple golfs, which I think should work: Try it online! \$\endgroup\$
    – pxeger
    Jun 24 at 15:21
  • \$\begingroup\$ Could you say how it works? I notice it is not recursive. \$\endgroup\$
    – felipa
    Jun 24 at 16:14
5
\$\begingroup\$

Python 3, 394 378 bytes

thanks @Anush for finding issues

thanks @pxeger for -16 bytes

def f(x,c):
 A,B=zip(*x);r=len(x);l=o=0
 if c>=sum(B):return sum(A)
 while 1:
  a,b=x[__import__('random').randint(l,r-1)];t=a/b;W=P=0;i=k=l;j=r
  while k<j:
   p,w=x[k];u=v=k
   if p/w>t:v=i;i+=1;W+=w;P+=p
   elif p/w<t:j-=1;v=j;k-=1
   k+=1;x[u],x[v]=x[v],x[u]
  if W>c:r=i;continue
  while W<c and i<j:p,w=x[i];i+=1;W+=w;P+=p
  if W>=c:return(c-W+w)*p/w+P-p+o
  l=j;c-=W;o+=P

Try it online!

non-competing. qselect with in-place 3-way partitioning.

x list of price-weight pairs

c capacity

l r left and right index in x (everywhere it's left inclusive, right exclusive)

t pivot

i j 3-way partitioning:

  • x[l:i] are larger than t
  • x[i:j] are equal to t
  • x[j:r] are smaller than t

k current index

p price

w weight

P partial sum of prices

W partial sum of weights

o accumulator for the result

u v temporary

\$\endgroup\$
11
  • \$\begingroup\$ Why is it not competing? \$\endgroup\$
    – Anush
    Jun 24 at 17:28
  • 1
    \$\begingroup\$ @Anush it sacrifices conciseness for an in-place algorithm \$\endgroup\$
    – ngn
    Jun 24 at 17:34
  • 1
    \$\begingroup\$ Yes however this means (I assume) averaged over different runs of the code on the same data in the worst case. So take the worst input with respect to the running time,run the code an infinite number of times and measure the average running time. That's the standard definition of expected running time. Quicksort with a random pivot has O(n log n) expected running time for example. \$\endgroup\$
    – Anush
    Jun 25 at 9:17
  • 1
    \$\begingroup\$ @Anush fair enough. restored randomness and added special case for c>sum(weights) \$\endgroup\$
    – ngn
    Jun 25 at 11:13
  • 2
    \$\begingroup\$ A few golfs of the bugfix down to 378: Try it online! \$\endgroup\$
    – pxeger
    Jun 26 at 6:24
4
\$\begingroup\$

Common Lisp, 421 bytes

(defun F(F c)(loop for(p w)across(C F)sum p into R sum w into U until(> U c)finally(return(decf R(* p(min(/(- U c)w)1))))))(defun K(f)(floor(apply'/ f).01))(defun C(F)(reverse(let((C(make-array(1+(reduce'max(mapcar'K F))):initial-element 0))(O(make-array(length F))))(mapc(lambda(f)(incf(elt C(K f))))F)(dotimes(i(1-(length C)))(incf(elt C(1+ i))(elt C i)))(mapc(lambda(f)(setf(elt O(decf(elt C(K f))))f))(reverse F))O)))

Try it online!

Uses counting sort, should be \$O(n)\$ as far as I can tell.

F Main function & the list of input items of type f

f Individual items of format (profit weight)

c Capacity

p Profit of item

w Weight of item

U Total weight

R Total profit

K Helper function for calculating \$\left\lfloor 100\times p_i/w_i\right\rfloor\$ to use as index in C

C The counting sort & the array count[k+1]

O The output array in C

i Generic index

\$\endgroup\$
4
  • \$\begingroup\$ What are you sorting by counting sort? \$\endgroup\$
    – Anush
    Jul 3 at 6:28
  • \$\begingroup\$ The reason I ask is that the obvious thing to sort (profit/weight) is not an integer and counting sort needs integers. \$\endgroup\$
    – Anush
    Jul 3 at 8:16
  • 1
    \$\begingroup\$ @Anush Yes I'm sorting the result of the K function, that is, \$\left\lfloor100\times p_i/w_i\right\rfloor\$. It's of course possible to increase the multiplier but 100 is decent enough to get \$\pm 0.01\$ \$\endgroup\$
    – Thun_A
    Jul 3 at 8:42
  • \$\begingroup\$ Oh I see! Thanks. \$\endgroup\$
    – Anush
    Jul 3 at 8:49
3
\$\begingroup\$

R, 172 178 bytes

f=function(x,m,y=x$p/x$w,s=sample(c(y,y),1),S=sum,i=`if`)i((v=S((z<-x[y>s,])$w))>m,f(z,m),i((t=v+S((u=x[y==s,])$w))>=m,S(z$p)+(m-v)*s,S(c(z$p,u$p))+i(any(y<s),f(x[y<s,],m-t),0)))

Try it online!

A function that takes a data frame x with columns w and p and a capacity m and returns a double indicating the profit. As far as I can tell, this should be \$O(n)\$ complexity. Thanks to @digEmAll for saving 9 bytes! Thanks to @Anush for pointing out that the original version failed where everything can fit in the knapsack.

\$\endgroup\$
4
  • \$\begingroup\$ I think your code fails with capacity 60000. Is that right? \$\endgroup\$
    – Anush
    Jun 25 at 10:00
  • \$\begingroup\$ @Anush I don’t think so - what makes you think that? \$\endgroup\$ Jun 25 at 10:36
  • \$\begingroup\$ I blindly changed 995 to 60000 in the TIO. Can you give a link with it working? Also it seems slow for a liner time solution. Can you explain how your code works please. \$\endgroup\$
    – Anush
    Jun 25 at 10:37
  • \$\begingroup\$ @Anush I see. I hadn’t appreciated you meant where the capacity exceeded the items. I’ve now fixed it so it works for that situation too. \$\endgroup\$ Jun 25 at 11:57
2
+50
\$\begingroup\$

C++ (clang), 410 \$\cdots\$ 323 321 bytes

#import<bits/stdc++.h>
using V=std::deque<std::pair<float,int>>;float f(int W,V&l){int N=0,X=0,A=0,i=0;auto[a,b]=l[rand()%l.size()];V L,S,M;for(auto t:l){auto[p,w]=t;(p/w>a/b?N+=p,A=X+=w,L:p/w==a/b?++i,M:S).push_back(t);}for(;i--&X<W;X+=b)std::tie(a,b)=M[i],N+=a;return A>W?f(W,L):X<W?S>V()?f(W-X,S)+N:N:(W-X+b)*a/b+N-a;}

Try it online!

Saved a whopping 24 25 31 33 bytes thanks to ceilingcat!!!

Port of my Python answer.

\$\endgroup\$
5
  • \$\begingroup\$ Someone else will have to give answers in two languages from the list to beat this \$\endgroup\$
    – Anush
    Jun 28 at 18:55
  • \$\begingroup\$ @Anush It could be faster but since it's code golf had to cut corners. Still \$O(n)\$ which is the main goal! :D \$\endgroup\$
    – Noodle9
    Jun 28 at 20:43
  • \$\begingroup\$ How could it be faster? \$\endgroup\$
    – Anush
    Jun 28 at 20:50
  • 2
    \$\begingroup\$ @Anush std::vector would be a better choice of container over std::deque but not only is its name shorter, can do the std::tie(a,b)=M[0],M.pop_front() golf with std::deque. You can't pop from the front of a std::vector so it has to be std::tie(a,b)=M.back(),M.pop_back(). Also golfing all cases into a single return is slower than returning earlier for A>W. Also constructing the L;M;S to max size would be faster than doing push_back into growing containers. \$\endgroup\$
    – Noodle9
    Jun 28 at 21:07
  • \$\begingroup\$ @ceilingcat Nice golf - thanks! :D \$\endgroup\$
    – Noodle9
    Jul 8 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.