Clojurians Log v2

I found this example of using PyGLPK (a Python binding to GLPK) and it looks like something I could employ - optimizing a multivariate function https://web.archive.org/web/20200217210502/http://tfinley.net/software/pyglpk/discussion.html

need to look if there are Java/Clojure bindings to GLPK or maybe I could use it with FFI

For maximizing these types of problems mixed integer programming (MIP) is a good fit. Your problem indeed sounds like a variation of the knapsack problem, which is NP-complete, but modern MIP solvers can find the maxima as long as the problem is not too large. There are decades of clever math and optimizations built into these solvers I'm not aware of any clojure libraries, but google OR-tools (python library) or Minizinc (custom modelling language + IDE) are fairly simple to get started with.

Incorrect, this is not using iteration is using recursion to explode tree of combinations (maybe replacing "recur" with call will make it more obvious), then is picking the combination with maxvalue by comparing each branches. If you squint, you will notice this follow the same solution shape as the classic "change problem" which explodes all possible results. Also is not using the ratio as the classic greedy solution does. It does have other problems though, but for small cases it will get the optimum

I think core.logic will not really make it easier to avoid the brute force search. AFAIK it doesn't have constraint programming or anything that would help with the optimization problem

Do you know any other libraries that could help?

Unfortunately no. Java probably has something but I have no experience there. You formulated the problem well so I would suggest asking ChatGPT

at least it doesn't do DFS but interleaving the branches, so if there is a solution, it should find it and not go down the rabbit hole first.

this sound a lot like https://en.wikipedia.org/wiki/Knapsack_problem which is NP-Complete

is it greedy? 🤔 I intend it to make a combinatoric explosion 🧨, maybe I'm missing something 😆 Which part of the tree is being discarded?

max value picks the highest value at each iteration

If had to write a brute force version, assuming items can only be picked once, I would attempt something like this: (did not test, might be buggy)

(defn max-value [sol1 sol2]
  (if (> (:value sol1)
         (:value sol2))
    sol1
    sol2))

(defn brute-knapsack [{:keys [total-weight total-value selected items] :as sol}]
 (if-let [[{:keys [value weight] :as item} & items'] (seq items)]
   (if (> 0 (- total-weight weight))
       (max-value (brute-knapsack (assoc sol
                                         :items items'))
                  (brute-knapsack (assoc sol
                                         :items items'
                                         :selected (conj item selected)
                                         :total-value (+ total-value value)
                                         :total-weight (- total-weight weight))))
       (brute-knapsack (assoc sol :items items'))) ;; edited (recur (assoc sol :items items'))
   sol))

this is just a greedy estimate, it might not return the optimal value

I’m no expert, but I wonder if this is the kind of thing a constraint solver would be good for. z3 is a popular choice, and it has Java bindings.

As Wikipedia article says there is no know algorithm that is correct and fast at the same time. you can program this with a constraint language, core.logic or even just recursion, but it wont be efficient neither in terms of memory nor in terms of time. For a small enough case, you might not even care about resource utilization. Or for a large case incorrect but "good enough" might be sufficient.

While the theoretical complexity of these algos is poor, in practice, constraint programming systems like z3 can achieve reasonable results on many problems, either by being very clever about how they approach the search space, or by not provably guaranteeing an optimal answer (though they do in practice usually produce the optimal answer)