Is this Knapsack/Subset Sum Variant NP-Hard?

The problem: Let $$A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$$ be $$k$$ sets of $$n$$ integers, and let $$U,L \in \mathbb{N}$$ be integer parameters. Assume that for all $$i \in [k]$$ it holds that $$a^i_1 \leq a^i_2 \leq \ldots \leq a^i_n$$. The goal is to find $$r_1,\ldots,r_k \in [n]$$ (possibly with repetition) such that

$$\sum_{i \in [k]} \sum_{j \in [r_i]} a^i_j \leq U, ~~~\sum_{i \in [k]} \sum_{j \in [r_i]} a^i_{n-j+1} \geq L.$$

In words, we take $$k$$ prefixes, one for each set, according to a sorted way, and we want that the total sum of the prefixes to be upper bounded by $$U$$; at the same time, we want that the total sum of the corresponding suffixes (e.g., the corresponding suffix of $$a^i_1,a^i_2$$ is $$a^i_n,a^i_{n-1}$$) to be lower bounded by $$L$$.

Question: Is this problem NP-Hard?

• Can we reduce from partition with a set $S$ by setting $n=1$, $A_i = \{s_i\}$ for all $i$, and $U = L = \sum_{s\in S} s/2$?
– SamM
Jun 10, 2023 at 16:16
• Seems like a nice homework question. Jun 18, 2023 at 10:31