How can you solve this kind of algorithm problem? (The set purchasing problem-solving)-CodePudding

I just saw a kind of algorithm problem like the one below. I don't know how to solve it efficiently so I want to listen to your opinion.

The problem is that you should find the cheapest price to buy certain (at least) quantities of tomatoes when you can only buy with the set like below.

Objective : Buy at least 41 tomatoes
Set A : 14,000$ with 10 tomatoes (1,400$ per each)
Set B : 15,000$ with 8 tomatoes (1,875$ per each)
Set C : 12,000$ with 3 tomatoes (4,000$ per each)

I just thought at first that I should buy the cheapest per each set as many as under quantities(in this case, 40), and think about the rest cases (like 1 Set B or 1 Set C...) but it was wrong since the answer was 3 Set A, 1 Set B, 1 Set C (total price 69,000$).

So I wonder if I should consider all possible purchase cases which are over condition quantities to know that. If then, is there any way to know when to stop the case searching (I mean optimization of searching)?

CodePudding user response：

This is a bin packing / kansack problem. Just google for it.