Minimum number of guards
Hey guys!
Let's say we have n elements.
1 2 3 4 ... n
Every element has different value
10, 20, 13, 17 ... 12
How would you distribute minimum amount of guards to guard all the elements if one guard can only cover one element and it's neighbours. For example if you place guard on element 2 he can cover elements 1,2,3. Also every guard can only guard n% of total value of the elements.
I don't need the code I just need the ideas on how to solve this problem.
Thanks
Let's say we have n elements.
1 2 3 4 ... n
Every element has different value
10, 20, 13, 17 ... 12
How would you distribute minimum amount of guards to guard all the elements if one guard can only cover one element and it's neighbours. For example if you place guard on element 2 he can cover elements 1,2,3. Also every guard can only guard n% of total value of the elements.
I don't need the code I just need the ideas on how to solve this problem.
Thanks
You can try putting them into an array/vector and check for the n%(I dunno what you mean by n here, but I'll guess it's not the n in n elements). Prior to the distribution of guards, check for the minimum number of guards to be allocated. You can use guards = n/(1+n%) (depending on what your n% distribution means), then allocate and distribute them to your guards(or guards to them), which should be dynamic btw.
Lets say we have 4 elements: A, B, C, D
Values of elements (random for this example):
A=100€
B=200€
C=100€
D=100€
Total value is: 100 + 200 + 100 + 100 = 500€
if n = 20, then every guard can only guard 20% of total value 500€. So every guard can guard a total amount of 100€
So if we place guard #1 on element B we can see that he can't guard all three elements that are around him because the total value of them is 400€ (A+B+C) while he can only guard a total of 100€.
I think I found the solution if you only place guard on 2. and n-1 place at the begining and then decrese the values of first and last elements until they are 0. If you ran out of guards you add new ones.
Values of elements (random for this example):
A=100€
B=200€
C=100€
D=100€
Total value is: 100 + 200 + 100 + 100 = 500€
if n = 20, then every guard can only guard 20% of total value 500€. So every guard can guard a total amount of 100€
So if we place guard #1 on element B we can see that he can't guard all three elements that are around him because the total value of them is 400€ (A+B+C) while he can only guard a total of 100€.
I think I found the solution if you only place guard on 2. and n-1 place at the begining and then decrese the values of first and last elements until they are 0. If you ran out of guards you add new ones.
It logically doesn't make any sense to place any guards on the ends, since it's more effective to put them one off the ends.
IE, with your ABCD scenario, you don't ever need to put any guards on A or D... since a guard on B is more effective than a guard on A, and a guard on C is more effective than a guard on D.
So really, this problem is very simple.
- Start with position B and place as many guards to satisfy A
- Then move to position C and place as many to satisfy position B
- and so on until you get to the 2nd to last element -- where you would add guards to satisfy all 3 of the last elements.
In your case, we'd start with this:
guards can guard 100 each
Step 1: put enough guards on B to satisfy A:
Step 2: Place enough on C to satisfy B:
Step 3: Place enough on the 2nd to last element (C) to satisfy the last elements:
EDIT:
It works with more complex setups also:
Fill B to guard A:
Fill C to guard B:
Fill D to guard C:
Add more to D to guard D&E:
IE, with your ABCD scenario, you don't ever need to put any guards on A or D... since a guard on B is more effective than a guard on A, and a guard on C is more effective than a guard on D.
So really, this problem is very simple.
- Start with position B and place as many guards to satisfy A
- Then move to position C and place as many to satisfy position B
- and so on until you get to the 2nd to last element -- where you would add guards to satisfy all 3 of the last elements.
In your case, we'd start with this:
A = 0 guards, 100 unguarded B = 0 guards, 200 unguarded C = 0 guards, 100 unguarded D = 0 guards, 100 unguarded |
guards can guard 100 each
Step 1: put enough guards on B to satisfy A:
A = 0 guards, 0 unguarded B = 1 guard , 200 unguarded C = 0 guards, 100 unguarded D = 0 guards, 100 unguarded |
Step 2: Place enough on C to satisfy B:
A = 0 guards, 0 unguarded B = 1 guard , 0 unguarded C = 2 guards, 100 unguarded D = 0 guards, 100 unguarded |
Step 3: Place enough on the 2nd to last element (C) to satisfy the last elements:
A = 0 guards, 0 unguarded B = 1 guard , 0 unguarded C = 4 guards, 0 unguarded D = 0 guards, 0 unguarded |
EDIT:
It works with more complex setups also:
Each guard can guard $10 A = 0, $65 B = 0, $42 C = 0, $116 D = 0, $8 E = 0, $51 |
Fill B to guard A:
A = 0, $0 (-$65) B = 7, $37 (+7 guards, -$5) C = 0, $116 D = 0, $8 E = 0, $51 |
Fill C to guard B:
A = 0, $0 B = 7, $0 (-$37) C = 4, $113 (+4, -$3) D = 0, $8 E = 0, $51 |
Fill D to guard C:
A = 0, $0 B = 7, $0 C = 4, $0 (-$113) D = 12, $1 (+12, -$7) E = 0, $51 |
Add more to D to guard D&E:
A = 0, $0
B = 7, $0
C = 4, $0
D = 18, $0 (+6, -$1)
E = 0, $0 (-$51)
(8 guard units wasted)
|
Last edited on
test your code with this input:
A 12
B 10
C 15
D 6
E 7
n=5; total = 50; guardCapacity = 50*(n/100) = 10.
sample solution:
A ##
B #
C ##
D #
E #
above solution needs 7 guards.
its not optimal solution because its possible to solve using fewer guards.
find by your program.
find the minimum guard number.
(its possible to have different possitions for min guards, find at least one of them)
A 12
B 10
C 15
D 6
E 7
n=5; total = 50; guardCapacity = 50*(n/100) = 10.
sample solution:
A ##
B #
C ##
D #
E #
above solution needs 7 guards.
its not optimal solution because its possible to solve using fewer guards.
find by your program.
find the minimum guard number.
(its possible to have different possitions for min guards, find at least one of them)
Wow thanks for the response guys. I think I found the optimal solution for the example above.
Disch yes I got the same results but my solution was more complex so it's cool that there is even easier solution.
Do you get the same result for:
A=100€
B=200€
C=100€
D=400€
E=500€
total = 1300
n = 30% -> each guard can guard 390€
A: 0 guards
B: 1 guard
C: 0 guards
D: 3 guards
E: 0 guards
solution: 4 guards (above is only one of the options ofcourse)
Disch yes I got the same results but my solution was more complex so it's cool that there is even easier solution.
Do you get the same result for:
A=100€
B=200€
C=100€
D=400€
E=500€
total = 1300
n = 30% -> each guard can guard 390€
A: 0 guards
B: 1 guard
C: 0 guards
D: 3 guards
E: 0 guards
solution: 4 guards (above is only one of the options ofcourse)
Last edited on
anup30 n is user input in range 0 -100% from n you calculate how much value one guard can guard
| Do you get the same result for: |
Let's see!
Setup:
A = 0, $100 B = 0, $200 C = 0, $100 D = 0, $400 E = 0, $500 guard = $390 coverage |
Step 1 (satisfy A):
A = 0, $0 (-$100) B = 1, $0 (+1, -$200) C = 0, $10 (-$90) D = 0, $400 E = 0, $500 |
Step 2 (satisfy B):
[skipped - B is satisfied]
Step 3 (satisfy C):
A = 0, $0 B = 1, $0 C = 0, $0 (-$10) D = 1, $20 (+1, -$380) E = 0, $500 |
Step 4 (satisfy D & E):
A = 0, $0 B = 1, $0 C = 0, $0 D = 3, $0 (+2, -$20) E = 0, $0 (-$500) (260 excess guard) |
So yeah -- same solution
Topic archived. No new replies allowed.