Searching Algorithm: Product Knapsack Problem with goal to find lowest product above a certain threshold?

Question

I'm looking for people with some algorithmic knowledge who can help me out with this.

I'm currently programming a constrained tree search in java, where I want to have a certain amount of leaf nodes that is just bigger than a given threshold T.

I'm boiling down the problem (which is most likely NP complete) to this:

Problem

Input: a threshold T, and a List of entries L = [e₁, e₂, ..., e_n], where for every e_i (where 1 <= i <= n) there is a defined arbitrary maximum weight wMax_i and a minimum weight wMin_i = 1. (wMax_i >= wMin_i)

Output: a choice of weights w_i, so that:

• wMax_i >= w_i >= wMin_i = 1
• the product W of w_i is greater than threshold (W > T)
• the product of w_i is lowest possible or if not possible is linearly constrained in T (W is in O(T) / W < k * T)

Notes

• all numbers are integers here
• it will always be true that the product of wMax_i W_max >> T
• it would be highly preferable to find a solution where the w_i are evenly distributed, meaning that I would rather have [2,2,2,2 ...] than [4,1,4,1, ...], this would be even more preferred over finding a solution with lowest possible W as long as it's linearly constrained.

I tried to approximate the solution when defining this problem with float numbers: every entry would be able to have a weight of ceil(log_n(T)) but this approximation doesn't work as the max weights are distributed quite unevenly.

Furthermore I read some articles on solving the product knapsack problem, but they were interested with achieving a max weight.

I'm also not so sure if this problem can be reduced to the knapsack problem, as the threshold is quite tricky to handle and I deal with products.

Edit: I ended up brute forcing it by iteratively and evenly increasing weights until I'm above T.

Edit:

Example data:

• entries: [e¹ ,e² , e³ , e⁴]
• weight_max respectively: [3,3,2,5]
• Threshold: T = 15

Solution (nearest Threshold):

• e1 = 1, e2 = 3, e2=1, e4 = 5 (Product 15)
• e1 = 3, e2 = 1, e2=1, e4 = 5 (Product 15)

Solution (as balanced as possible, while also near):

• e1 = 2, e2 = 2, e3 = 2, e4 = 2 (Product 16)

Answer 1

I have an algorithm similar to your brute force idea.

brute forcing it by iteratively and evenly increasing weights until I'm above T.

Let's do this, but using binary search instead. The algorithms goes something like this.

1. Sort by wMax_i
2. Define f(x) as the product of w_i where w_i = min(wMax_i, x). See below on how to compute f(x)
3. Binary search to find k where f(k) <= T and f(k+1) > T
4. Find the optimal i to "split" the list into k and k+1. So w_j = min(wMax_i, k) if j < i, and w_j = k+1 if j >= i. We can to find i such that the product is just above T with either linear or binary search

To compute f(x), a naive solution would suffice. But we can also compute the prefix product p_i, binary search for i where wMax_i < x and wMax_i+1 >= x. Then f(x) is equal to p_i plus x to the power of the number of elements left (watch out for off by 1 error).

The product is less than 2 * T. Also note that with this algorithm, the problem (where the product is not minimized but the variance/standard deviation of the weights is minimized) is not NP complete.