Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsFree MagazinesWhite PapersSubmit Content
Discussion GroupsASP.NETWindows FormsLanguages.NET FrameworkVisual Studio.NET
Articles.NET FrameworkASP.NETToolsWindows Forms
.NET DirectoryOpen Source ProjectsUser GroupsWeb Resources
Related Topics
Visual Basic 6SQL ServerMS AccessOther DB ProductsMS Server ProductsMore Topics ...

.NET Forum / Languages / C# / September 2007

Tip: Looking for answers? Try searching our database.

FINDING OUT WHAT'S LEFT

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
mattG - 12 Sep 2007 21:38 GMT
I have a scenario where I have these things that take up (x) number of
space.  I know the max number of space I will ever have is 512.  I am
trying to figure out a way to write a formula or whatever will make it
work to tell me how many of these things I can put in this space.

So example

I want to put 60 of these thing that take up (21) units each.  Well
given that I cannot go over 512 the max I am able to put in any one
space is 29.  I did the math to do that, but what sort of formula am I
looking for to do this.

I want to know how many of these things I can fit and what the next
available number for space is.  I have in the worksheet  a cell that
contains the number of units each different thing takes up because it
varies.

Thank you for any help.

Matt
mattG - 12 Sep 2007 21:40 GMT
> I have a scenario where I have these things that take up (x) number of
> space.  I know the max number of space I will ever have is 512.  I am
[quoted text clipped - 16 lines]
>
> Matt

correction to myself.  I would only fit 28 in the example
Doug Semler - 12 Sep 2007 21:49 GMT
> I have a scenario where I have these things that take up (x) number of
> space.  I know the max number of space I will ever have is 512.  I am
[quoted text clipped - 7 lines]
> space is 29.  I did the math to do that, but what sort of formula am I
> looking for to do this.

24, not 29.

> I want to know how many of these things I can fit and what the next
> available number for space is.  I have in the worksheet  a cell that
> contains the number of units each different thing takes up because it
> varies.

Look at integer division and mod operators.

int MaxSpace = 512;
int SpacePerItem = 21;

int itemCount = MaxSpace / SpacePerItem;
int spaceLeftOver = MaxSpace % SpacePerItem;
Peter Duniho - 12 Sep 2007 21:58 GMT
> I have a scenario where I have these things that take up (x) number of
> space.  I know the max number of space I will ever have is 512.  I am
[quoted text clipped - 7 lines]
> space is 29.  I did the math to do that, but what sort of formula am I
> looking for to do this.

What math did you do to figure out the 29, and what aspect of it are you
finding difficult to translate into code?  Are you sure you didn't come
up with 24, but then mis-read your handwriting as 29 instead?

You should be able to do a plain integer division (ie, no fraction,
decimal, remainder, etc.) to arrive at the correct number.  When I do
the math, I actually get 24 "things" that are 21 units large in a space
that is 512 units large.

The code is simple -- "int count = 512 / dxThingWidth" -- but telling
you that might not give you the tools you need to derive a similar line
of code in the future.  If you can explain why you weren't able to
translate the math you did into a line of code like that, that could
help you better understand how to do it successfully in the future (for
that matter, the act of explaining it may be sufficient for you to have
that "aha!" moment yourself).

Pete
Jon Slaughter - 13 Sep 2007 00:42 GMT
>I have a scenario where I have these things that take up (x) number of
> space.  I know the max number of space I will ever have is 512.  I am
[quoted text clipped - 16 lines]
>
> Matt

This is pretty simple if you think about it.

If you have x objects that take up y units then that is a total of x*y units
taken up... or x + x + x + x + ... + x where there are y x's in the sum.

To make this concrete, suppose you have 10 dollar bills and each dollar bill
is 4 quarter(or represents 4 units where are unit is the quarder), then

10 dollar bills * [4 quarters / 1 dollar bill] = 40 quarters.

notice that I used dimensional analysis here. What this means is that I
treat the "dimension"(this case its dollars and quarters) which represents
what type of object the number is as sorta its own "number" that can be used
like a number.

That probably doesn't make sense but realize that

4 quarters / 1 dollar bill = 1

because

4 quarters = 1 dollar bill. (dividing both sides by the same amount is a
valid mathematical operation)

So essnetially what I did was start with

10 dollar bills  = 10 dollar bills * 1

(multiplying by 1 doesn't change it)

but now I used

4 quarters / 1 dollar bill = 1

to get

10 dollar bills * [4 quarters / 1 dollar bill]

but then the dollar bill(s) cancel each other because have something like 10
* x * 4 * y / x = 10*4*y.

Which results in 40 quarters.

What that means is that

10 dollar bills = 40 quarters.
----------

Thats kinda a long explination but hopefully you understand it. (trying to
make it very simple so you can learn how to do this yourself)

If your a computer guy and know about bits and bytes you can do the same,

1000 bytes * [8 bits / byte] = 8000 bits

i.e., 1000 bytes is the same as 8000 bits.
-----------

Your problem is the exact same but a different perspective

x objects * [y space / object] = x*y space [for x objects]

i.e., x objects is the number of objects we are talking about
y space / object or y space / one object is the space taken by one object,
which is y.

The we multiply them and the units cancel and we are left with the total
space.
-----

For your specific problem

its 60*21 = 1260 units of space. (I left out the units in the product but I
know they are implicitly there)

Now if you have a max of 512 then you went over. By how much?

Well, its simple, we are looking for how many objects we can put into 512
because that would be our max.

i.e., x * 21 = 512. This gives us x = 24.123... but since x has to be an
integer(because we can't have partial objects), it means that we can have a
max of 24 units.

Notice that x = 512/21... but you can generalize this to be "Max
space"/"Size of one object".

Since you have 60 objects and 24 was the max then you are over by 60 - 24 =
36.

You can replace numbers with variables to make the equations more abstract
but more useful. If you don't know algebra then its about time to start
because this is what algebra is all about.
Lasse Vågsæther Karlsen - 14 Sep 2007 10:19 GMT
> I have a scenario where I have these things that take up (x) number of
> space.  I know the max number of space I will ever have is 512.  I am
[quoted text clipped - 16 lines]
>
> Matt

This is known as the "Knapsack problem", where you have a list of
objects, of varying size, and try to determine which ones to pack in
order to put the most items into the knapsack. I originally read, as did
all the others here, your question as "X items of the same size", but
your last sentences seems to indicate the sizes vary.

The problem usually ties a score to each item as well, and tries to
optimize the score while keeping the total size below or equal to the
space available in the knapsack.

As an example, you have the following items with their score and size:

A, score 5, size 3
B, score 7, size 4
C, score 2, size 1
D, score 4, size 2

You need to optimize the score while packing for a maximum size of 6.

A + B is too much
A + C + D gives a score of 11, size 6
B + C gives a score of 9, size 5
B + D gives a score of 11, size 6

This is an NP-Hard problem, and might thus require a simple brute-force
algorithm which, depending on the number of items, could take a long
time to run if you need the best packing. If you can live with a packing
that is not optimal but is at least above a certain threshold, a genetic
algorithm might be more appropriate.

A simple brute-force recursive algorithm could be:

keep track of max sum
ALG: pack items [items] into size [size]
.. for each item in [items] that fits into [size]
.... remove from [items]
.... reduce [size] with the items size
.... see if current sum of items removed is bigger than max sum
...... update max sum if yes
.... call algorithm with new [items] and new [size] (ie. minus the
removed item)
.... put back the item and increase size to restore item
.... go on to next item

Signature

Lasse Vågsæther Karlsen
mailto:lasse@vkarlsen.no


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.