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.
Best Answer
You said:
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$