# Proving that a greedy algorithm yields the optimal solution for a problem

I'm a college computer science student, working on a project. In my project i have an optimization problem, which i belive is optimally solveable with a greedy algorithm approach. In every case i have examined, the greedy algorithm yields the optimal solution, so i am fairly convinced it always will. I would like to mathematically prove that this is always the case.

To give abit of context, here is the problem explained.

Given two multisets, A and B, containing only positive integers, and target value m. Construct the minimum amout of sub-multisets, containing at most one member of B, and any amount of members from A, with each sub-multiset having a sum <= m. Note that each member in A and B, can only be used once.

Naive Example: A {3, 3, 4, 5, 8}, B {2, 5}, m = 10

Solution: {5,5}, {2,8}, {3,3,4}

The greedy algorithm takes the highest value in B, computes the powerset of A and chooses the subset of A, subsetA, yielding the max-sum (subsetA + Bmax) <= m. Then removing subsetA and Bmax from A and B, and doing this over and over untill both sets are empty.

Since the goal is to empty the sets, the logic behind the algorithm, is to simply remove the largest (in terms of sum) possible subset of A over and over, paired with one member of B, over and over.

Me studying computer science, means that mathematic background is not the strongest. What techniques would one use to prove, that the above explained example yields the optimal solution to the problem (least amount of subsets)? Any help is appreciated, seeing i am abit stuck on this one.

You said:

In every case I have examined, the greedy algorithm yields the optimal solution, so I am fairly convinced it always will.

Don't be! (See also here: Examples of apparent patterns that eventually fail.)

Consider $B = \{\color{red}{2},\color{red}{2},\color{red}{2},\color{red}{2},\color{red}{2}\}$, $A = 5*\{7\} \cup 20*\{2\}$ and $m = 10$. Then your algorithm will produce $$5 * \{\color{red}{2},2,2,2,2\} \cup 5 * \{7\}$$ which is of size 10, while the optimal solution is of size 9: $$5*\{\color{red}{2},7\} \cup 4 * \{2,2,2,2,2\}.$$

I hope this helps $\ddot\smile$

• Also note that the easier problem obtained by setting $B=\emptyset$ is the bin packing problem which is known to be NP-hard. – m_l Nov 8 '13 at 16:55
• Thanks for the insight. Now that the method has been proven obsolete, do you have any suggestions for an approach to actually solve the problem correctly? – Emil Kongsgaard Nov 8 '13 at 18:56
• @EmilKongsgaard Not really, you might try some dynamic programming approach, but no algorithm would be polynomial unless $P = NP$, so brute-force might not be a bad option. If you don't need an exact solution, you may find some approximation algorithms, but that's a different story (check out the Wikipedia page that user m_l linked). – dtldarek Nov 8 '13 at 21:13