lotus 055ac26c3a revert cxxflags | 4 weeks ago | |
---|---|---|
include | 5 months ago | |
tests | 5 months ago | |
.clang_complete | 4 months ago | |
.gitignore | 5 months ago | |
.travis.yml | 3 months ago | |
README.md | 3 months ago | |
main.cpp | 5 months ago | |
makefile | 4 weeks ago | |
three.cpp | 5 months ago |
3 brothers have to transfer 9 boxes from one place to another. These boxes weigh 1, 2, 4, 5, 6, 8, 9, 11, 14 kilos.
Every brother takes 3 boxes.
Make a program that would count the most optimal way to take boxes? The difference between one brother’s carrying boxes weight and other’s has to be as small as it can be.
Since every brother has to take three boxes we cannot divide up the weight evenly. If there was not this requirement each brother could equally carry 20 kilos. Since each brother must carry three boxes they will not all carry the same total weight.
Given that the weights of the boxes are growing linearly and do not appear to be random we can divide up the boxes without checking the weights.
Since the weights of the boxes are predictable as long as we are consistent with our box assignment we can minimize the disparity between weight distribution.
Also, with the given pattern of weights in the problem, we can extrapolate this and accept any number of boxes to move.
This solution has a time complexity of O(n) since I only have to loop over my boxes once and can avoid comparing weights.
In the case where I am only given the first three weights, the time complexity goes up to O(2n) since I must go through and "put all my boxes in the room".
If the weights of the boxes changes to be something more random, or the boxes are unordered, this solution no longer works.
If the number of boxes in is not divisible by three than we move as many boxes as we can, leaving some left over.
make # regular release build
make debug # build fast with debug symbols enabled
make opt # build a optimized version
./three 24 1 3 5
# 24 boxes to move
# box 1 = 1 kilo
# box 2 = 3 kilos.
# box 3 = 5 kilos.