Am Montag, 4. März 2013 07:52:11 UTC+1 schrieb nand kishore:
I think DP soln would be :
int leastPay(int[] demands, int sum, int index) {
if(index == demands.length)
return sum;
else {
if(sum demands[index])
return leastPay(demands,
@immars , can you explain with some example or algorithm ?
Thanks
Shashank
On Tuesday, February 5, 2013 9:14:03 AM UTC+5:30, immars wrote:
suppose:
v : array of guards' request
P(n): our problem: least coin spent until guard n, according to these rules
M(n, x): least coin possibly
I think DP soln would be :
int leastPay(int[] demands, int sum, int index) {
if(index == demands.length)
return sum;
else {
if(sum demands[index])
return leastPay(demands, sum+demands[index], index+1);
else
return
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
@marti : can u please make problem statement clear .. give one example , we
can understand clearly
On Tue, Feb 5, 2013 at 9:14 AM, immars imm...@gmail.com wrote:
suppose:
v : array of guards' request
P(n): our problem: least coin spent until guard n, according to these rules
M(n, x):
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
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
suppose:
v : array of guards' request
P(n): our problem: least coin spent until guard n, according to these rules
M(n, x): least coin possibly combined equal to or larger than x until guard
n
then:
P(n) = min(P(n-1)+v[n], M(n-1, v[n]))
M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n])
On
This can be formulated as a 0-1 integer programming problem.
Define the matrix A such that a(i,j) = 1 if machine i is connected to
machine j, and = 0 otherwise (with the interpretation that every
machine is connected to itself).
Let x be a vector whose elements are in the set {0, 1}, where x(j)
The problem seems to be minimum dominating set problem (which is NP-complete
i think). But since the number of nodes will be =26, it can be solved by
some intelligent brute force.
Something like this might work:
Take all subsets of the given nodes. Iteratively keep increasing the size of
the
10 matches
Mail list logo
