Inputs V1n an array of floating point numbers not necessari

Inputs:
? V[1..n], an array of floating point numbers (not necessarily non-negative), where the ith entry in the array corresponds to the total value of the ith type of glitter in the store.
? Q[1..n], an array of non-negative integers, where the Q[i] equals the number of quarts of the ith type of glitter in the store.
? k, the number of quart ziplock bags that our thief has

Return: X[1..n], an array of integers where the ith entry in the array indicates the amount of a type of glitter that is stolen, such that X that maximizes the profit for the thief. The thief’s profit is given by the following quantity:

a) Provide a greedy algorithm that correctly solves this problem. Your solution must be written as an algorithm (not computer code). You must provide sufficient detail to clearly show how your algorithm works AND to analyze the running time of your algorithm
b) Express the worst case running time of your algorithm in part 1 using big O notation. Make your bounds as tight as possible.
c) provide a proof by contradiction to argue for the partial correctness of your algorithm.

Solution

a) Provide a greedy algorithm that correctly solves this problem.Your solution must be written as an algorithm (not computer code).
You must provide sufficient detail to clearly show how your algorithm works AND to analyze the running time of your algorithm

Input for algoirthum

Case 1:

V[5] = { 1,2,3,4,5 }
Q[5] = { 20,15,12,9,3}

Case 2:

V[5] = {1,2,3,4,5}
Q[5] = {5,7,9,12,20}

case 3:

v[5] = {1,2,3,4,5}
Q[5] = {4,9,20,12,3}

Step 1 : Below Assumption are taken.

   A) Let\'s assume that we have the above array of items and their quantity in store.
   B) Here selection will start from first type of glitter avaibale in stroe i.e first position of array.
   C) Always makes the choice that looks best at that moment.
   D) Once thief makes selection, he cannot go back or greed approch shoudl be there.
     
Step 2 : Find the possibilites to steal the maximum quantities of gilters so that maximum profit can be made.
  
   Let\'s assume that three possible senarios are there where thief can steal maiximum gilters.
  
   Case 1 :
       First type gilter have maximum quanities avaiable in store and that\'s why thief can stole the v[1] type gilter with (n-1) quantities
       where n is the number of gilter avaibale in store.
         
       Q[0] have n mumber of gilters of type v[0] thief can steal n-1 number of item.  

   Case 2 : Last type of gilter have maximum quanities avaiable in store and that\'s why thief can stole the v[1] type gilter with (n-1) quantities
       where n is the number of gilter avaibale in store.
  
       Q[m] have n mumber of gilters of type v[m] thief can steal n-1 number of item.

    Case 3 : Midddle of array item having maximum quanities avaiable in store ( i.e if 5 item are in array then 3rd or v[2] typem gillter has maximum quantities.
             
       Q[m+1/2] have n mumber of gilters of type v[m] thief can steal n-1 number of item.
         
  
Step 3 : Now We have three more cases where we can say that maximum costly gilters can be placed in store according to following logic.
       Case 1 : Maximum price or amount of gilter type is avaialble at first index.

           X[0] have highest costly product avaibale in store.

       Case 2 : Maximum price or amount of gilter type is avaialble at last index.
          
           x[m] have highest costly product avaibale in store.

       Case 3 : Maximum price or amount of gilter type is avaialble at the middle of the array.

           X[M+1/2] have highest costly product avaibale in store.

Step 4 : profit calculation

      
       Best Case :

           If thief steal maximum number of gilters having highest costly item or product or gilter which are placed at first position.  

       Avaerage Case :

           If thief steal maximum number of gilters having highest costly item or product or gilter which are placed at middle of array.
      
       Worst Case :
             
           If thief steal maximum number of gilters having highest costly item or product or gilter which are placed at last index of array.
  

B)

Worst Case Analysis (Usually Done)
In the worst case analysis, we calculate upper bound on running time of an algorithm.
We must know that the thief steal maximum number of gilters having highest costly item or product or gilter which are placed at last index of array
so the possilbilites of steal the highest costley item with maximum quantites is very less or O(n).

We have to devide the sum of all the quantities say n where m is the number of costly item.