#knapsack — Public Fediverse posts

Approximately Counting Knapsack Solutions in Subquadratic Time http://arxiv.org/abs/2410.22267v1

Authors: Weiming Feng, Ce JinWe revisit the classic #Knapsack problem, which asks to count the Boolean
points $(x_1,dots,x_n)in{0,1}^n$ in a given half-space
$sum_{i=1}^nW_ix_ile T$. This #P-complete problem admits
$(1pmepsilon)$-approximation. Before this work, [Dyer, STOC 2003]'s
$tilde{O}(n^{2.5}+n^2{epsilon^{-2}})$-time randomized approximation scheme
remains the fastest known in the

Solving the knapsack problem with @ApacheGroovy
https://groovy.apache.org/blog/groovy-knapsack
#groovylang #optimization #chocosolver #knapsack #ortools