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 <
saurabh.paliwa...@gmail.com> 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 <amritsa...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
