How do you make a combination for this problem?

Question

You have $11$ bags which you can load with money. In the first bag, there's \$$1$(cannot be changed), and you will be asked to load these bags with money I want between $1-2000$ (Which is like $1447$, $1550$, $27$ or anything other, so it doesn't matter.) Note that the total sum of the money you load will be equal to $2000$ and you need to fill each bags.

The thing made me confused is can we give every money he wants? For example, I'll pick a random value, which is $1447$.

$$1 / 2 / 3 / 4 / 5 / 10 / 25 / 50 / 100/800/1000 = \$2000$$ I could try giving him

$$ 1000 + 100 + 50 + 25 + 10 + 5 + 4 + 2 + 1 \neq \$1447 $$

Which is not equal to the value I selected.

As you can see, I couldn't be able to give that money. This question should have an easy solution I'm missing! Can you take a look since you are advanced?

My Kindest Regards!

Answer 1

There is no need to put \$3 in the third bag. If you are asked for exactly \$3, you could hand over the first two bags. Thus you could put \$4 in the third bag. Similarly, with bags containing \$1, \$2, and \$4 you can obtain any dollar amount between \$1 and \$7. So the fourth bag should contain \$8.

Proceed in this manner, and the dollar amounts in the first 10 bags will be $$ \$ 1 , \$2, \$4, \$8, \$16, \$32, \$64, \$128, \$256, \$512.$$

You can use these bags to make any dollar amount between \$1 and \$1023.

Now place the remaining \$977 into the eleventh bag. You can make any dollar amount between \$977 and \$2000 using the eleventh bag and an appropriate selection of bags between 1 and 10.

Answer 2

I suggest that you should fill the each bag as full as you can stuff it, yet still be able to deliver on all of the orders less than that bag size. This will allow you to fill the largest number of orders with the fewest number of bags.

The first bag has $\$1.$ What if you are asked to deliver $\$2$? You better have a bag with 2 bucks in it. This is a more efficient use of the limited resource (the limited number of bags) than having a second bag with $\$1.$

What if you are asked to deliver $\$3$? Easy, give bags $1$ and $2.$

What if you are asked to deliver $\$4$? Can't do that with what you have already allocated. You will need to fill another bag, and fill it with $4$ dollars.

With bags 1,2,3 you can fill orders up to $7$ dollars, but you can't fill the $8$ dollar order.

Have you spotted a pattern yet? Can you prove that by this pattern, you can fill any size order less than $\$2000$?

Answer 3

The answer should be like that; 1,2,4,8,16,32,128,256,512,1024

But since you said that you need a sum of 2000, you can make 973 instaed of 1024. you can also play around with the other numbers. The key is, that you should choose the next number to be 1 bigger than the sum of all numbers that you have so far, or less than that, but not bigger.

for example, 1,2,4,8,16,32,64,128,256,490,999.