Continuous knapsack but fast

Question

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 code-golf challenge, so the shortest submission in bytes per language wins, but the complexity is restricted to linear.

Answer 1

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)

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

C++ (clang), ^{410 \$\cdots\$ 310} 302 bytes

#import<regex>
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[p,w]:l)(p/w>a/b?N+=p,A=X+=w,L:p/w==a/b?++i,M:S).push_back({p,w});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)*a/b+N;}

Try it online!

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

Port of my Python answer.