2
$\begingroup$

Problem Description: we have an array of n positive integers and in one operation we have to choose two elements in the array and decrease them by 1. (Elements on which we are performing this operation must be positive). How can we do this operation on this array repeatedly as many times as possible?

Greedy Algorithm: we repeatedly choose two largest elements in the array and decrement them by 1. The final array will have all elements equal to zero or will have exactly one nonzero element ([0,0,.....,0] or ([0,0,...,0,x,0,...,0], x is positive integer).

Argument is if (Array[j] == largest element in array) >= (sum of Array[i] for all i != j), then the max_operation = (sum of Array[i] for all i != j). Otherwise the largest is less than that sum, then new_Sum = ∑Array[i]; 1<=i<=n ; max_operations = (Integer)(new_sum/2);

My confusion: I am not able to understand why this algorithm works. How can i prove this algorithm for 2nd case that max_operations = (Integer)(new_sum/2). What is the correct proof for this greedy algorithm?

Example: Array = [1,2,3,4], int operations = 0;
first picking indices(index starts with 0) 2,3 and subtracting 1 ; so now Array becomes [1,2,2,3], operations = 0+1 = 1;
(picking indices 2,3 , Array = [1,2,1,2] , operations = 1+1 = 2;)
(picking indices 1,3 , Array = [1,1,1,1] , operations = 2+1 = 3;)
(picking indices 0,1 , Array = [0,0,1,1] , operations = 3+1 = 4;)
(picking indices 2,3 , Array = [0,0,0,0] , operations= 4+1 = 5;)

For more information, here is the original problem.

$\endgroup$
2
$\begingroup$

The goal is to make sure the one remaining element is as small as possible (if there is one). So as long as you reduce the 2 largest elements every step you will get to the lowest remaining element possible?

I'm not sure more than this is necessary to "prove" it.

$\endgroup$
1
  • $\begingroup$ While this answer explains the idea of the greedy algorithm concisely, could it be called a proof? $\endgroup$
    – John L.
    Nov 6 '21 at 3:26
1
$\begingroup$

Once we have played with the operations for a few times, we will soon realize that too large an element may not be able to pair with all other elements. So, while the end goal is to perform as many operations as possible, the immediate goal in each step could be reducing the largest element. Furthermore, we would like to reduce the next largest element as well, since it might become the largest element later. That is how we may find the greedy algorithm described in the question, which picks the two largest element in each step.

The question is how we can prove rigorously that greedy algorithm does work.


At each point of time when the algorithm is running,

  • let $b$ be the biggest value of all elements, or 0 if there is no elements.
  • let $r$ be the sum of all (non-zero) elements except one element that is equal to $b$ , or 0 if there is only one non-zero element.

Case I, $b>r+1$ initially (Easier Case)

Suppose $b$ is $a_i$ for some $i$ initially. Every operation must include an element other than $a_i$. The sum of all elements other than $a_i$ is $r$ initially. So the most operations possible is (the initial) $r$.

Any algorithm that always pair $a_i$ with another element will perform (the initial) $r$ operations. In particular, the greedy algorithm will perform the most operations.

Case II, $b\le r+1$ initially

Claim. During a run of the greedy algorithm, it is always true that $b\le r+1$.

Intuitively, the claim makes sense since each operation will reduce the two largest elements. Instead of reading the short proof below, it is probably faster for you to prove the claim is true by yourself.

Proof. Suppose $b\le r+1$ at some step. The greedy algorithm will reduce the two largest elements (so we have $r>0 $). We will show that $b\le r+1$ still hold after the operation.

  • If the largest element is unique, then both $b$ and $r$ will be reduced by $1$. $b\le r+1$ after the operation.
  • Otherwise, there are at least two elements of the biggest value. WLOG, let them be $b_1$ and $b_2$, which will be reduced. After the operation, either $b_1-1$ or $b_2-1$ is a summand of $r$ while $b$ is as most as big as $b_1$. So $b\le r+1$ after the operation. $\checkmark$.

Consider a greedy run. When the run stops, $r$ must be 0; Otherwise, there are at least two nonzero elements, which means another operation can be made. Thanks to the claim, $b$ must be either $0$ or $1$. So the sum of all elements at the end, i.e., $b+r$ is

  • either $0$, which is, of course, the least possible,
  • or $1$, which is also the least possible, since the the sum of all elements was odd initially and has been staying odd all the time.

Since each operation reduces the sum of all elements by $2$, the maximum number of operations corresponds to reducing the sum of all elements as much as possible. So the greedy algorithm performs the maximum number of operations.


Exercise. Suppose each operation will reduce three elements (instead of two elements) by 1 each. Design a greedy algorithm to perform as many operations as possible. Prove it is correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.