How can I choose the highest resulting combination out of arbitrary sized chunks, worth an arbitrary amount each

Question

I am given a set of companies that each want to buy my product in different sized chunks. I have a maximum of 28 Million units to sell and each company pays a different amount of money for their order. one pays 200 for every 2 million units chunks, one pay 400 for every 3.5 Million chunk, and so on.

I can sell as many units as I want to the same company, as long as it is in multiples of their order size (chunk).

How can I choose (how many chunks to sell to each what company) to get the most amount of revenue?

Answer 1

This appears to be a variant of the knapsack problem.

https://en.wikipedia.org/wiki/Knapsack_problem

You have a knapsack of 28 million units and you can "fill" it by selecting orders from companies where choosing an order of k units for m money takes up k space in your knapsack for a value of m revenue. If we assume that an order can be chosen many times, we'll get a different solution than if each order can only be chosen once. There's a dynamic programming solution that relies on building up a "globally optimal" choice of orders from smaller "locally optimal" choices of orders.