take this example
let the gaurds demand be
5 2 7 2 9
first guard : we have no choice but to give him 5
second guard : we have choice , either skip him and pay 7 to next guard or
pay him and save 7 from third guard .. thus clearly multiple solutions
exist but we have to give optimal one. { hint for dp }
if we know the solution for upto i-th guard, we can extend this solution to
i+1-th guard
solution here represents all the possible amounts that one can spend till
i-th guard, extending that will give us all the possible amounts for i+1 th
guard and we just select the minimum amount. thus optimal substructure is
also there.
using the below code , the output for example is 12 with possible sequence.
guard 1 : 5
guard 2 : skip
guard 3 : 7
guard 4 :skip
guard 5 :skip
// non optimized code -purely for demonstration purpose -
#include <stdio.h>
#include <stdarg.h>
#define size 5
#define amount 10000000 // maximum amount asked by all the gaurds combined
int solution[size][amount];
int main (int argc, char const *argv[])
{
int arr[] = {5,2,7,2,9};
int min, i, j;
int sum = 0;
for(i = 0; i<size; i++) {
sum += arr[i];
}
solution[0][arr[0]] = 1;
for(i = 1; i< size; i++) {
for(j = 0; j<= sum; j++) {
if(solution[i-1][j] == 1) {
if(j > arr[i]) {
solution[i][j] = 1;
}
solution[i][j + arr[i]] = 1;
}
}
}
min = 1000000000; // infinite value
for(i = 0; i < sum; i++) {
if(solution[size - 1][i] && i < min)
min = i;
}
printf("%d", min);
return 0;
}
@marti check the solution for other testcases , I'll post the optimized
version after that.
On Wed, Feb 27, 2013 at 1:04 AM, Saurabh Paliwal <
[email protected]> wrote:
> Please mention the initial condition.
> I mean I wouldn't pay to any guard (assuming their demands are all
> positive numbers)
>
>
> On Wed, Feb 27, 2013 at 12:39 AM, marti <[email protected]> wrote:
>
>> Sure..
>> http://stackoverflow.com/questions/14686745/guards-and-demand
>>
>>
>>
>> On Monday, February 4, 2013 5:54:19 PM UTC+5:30, marti wrote:
>>>
>>> You have N guards in a line each with a demand of coins.You can skip
>>> paying a guard only if his demand is lesser than what you have totally paid
>>> before reaching him.Find the least number of coins you spend to cross all
>>> guards.
>>> I think its a DP problem but cant come up with a formula.Another
>>> approach would be to binary search on the answer but how do I verify if no.
>>> of coins is a possible answer?
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> - Saurabh Paliwal
>
> B-Tech. Comp. Science and Engg.
>
> IIT ROORKEE
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
