Value optimization is a defining principle of economic behavior. To uncover the underlying psychological and neural processes, we developed a behavioral task based on the ‘knapsack problem’. Given several items, each with a value and weight, the objective is to maximize value within the weight limit of the knapsack. Two rhesus monkeys solved a touchscreen-based version that equates weights with juice reward sizes. The animals performed well above chance and achieved at least 75% of the optimal reward value on 80% of all knapsack trials. We defined each unique set of items as an ‘instance,’ and estimated the difficulty of each instance. The animals adjusted their behavior based on the estimated difficulty. Specifically, they employed a ‘satisficing’ threshold that was lower when the difficulty was higher. Likewise, the animals took longer on individual selections and the entire solution when the difficulty was higher. These results indicate that the animals understood the complexity of the task and adjusted their behavior accordingly. To understand how the animals optimized, we categorized their solutions according to the solutions’ proximity to established computer algorithms. The greedy algorithm described the animals’ behavior on most trials. However, on approximately 15% of trials, combinatorial algorithms – and especially the Sahni-3 algorithm – provided the best match. During combinatorial trials, the animals spent more time deliberating, compared to noncombinatorial trials. Moreover, difficulty modulated deliberation time only during combinatorial trials. These results demonstrate that the animals adapted algorithmic strategies and employed combinatorial reasoning. Feedforward neural networks trained to mimic the greedy and Sahni-3 algorithms, the dominant algorithmic matches to the animals’ behavior, showed stronger instance and solution representations, compared to networks trained to mimic other algorithms. These results establish a new behavioral paradigm for investigating the psychological and neural basis for combinatorial optimization and economic deliberation.