items and cost

[kumaresh_ana]

I have A containers. Each container has one coin of equal denomination (1 unit). I have B items to buy each costing 2, 3, 4, 6, 8 units.

I need to buy some items such that it follows something like a normal curve. ie. least cost and high cost items (say 2 , 8) are given lesser priority than nominal cost items (say 4).

I need to buy as many items as possible.

I know that I should buy least cost item to get maximum number of items. But the aim is not the only aim...


Let the number of items to be bought be near 60. And let N be 14.

[RoboTact]

I know that I should buy least cost item to get maximum number of items. But the aim is not the only aim...Unless you decide what's your criterion or at least explain it informally, problem is contradictory.

[kumaresh_ana]

Sorry guys. I did not complete the sentence. Let me reframe the problem.

I have N containers each having A coins of one unit denomination. Now, there are B types of items differing in cost (each type is of infinite in number). Now I give you a target number of items to buy, say X. The constraint to buy the items are

1. you need to buy atleast one item of each type.
2. the least cost and high cost items are to be of least priority.
3. the item with mean cost gets the highest priority.

(this is something like a normal curve)

[RoboTact]

So what's the problem with that?

[kumaresh_ana]

You have to give me the number of items that I whould buy of each type. (Isn't that obvious?).

[RoboTact]

It is, that's what my question about: what do you have trouble with implementing what you ask for?

[kumaresh_ana]

I do not know how to find the number of items of each type to buy satisfying the constraints. Can you help me out?

[RoboTact]

Anyway requirements should be better specified. If you'd show your efforts, some requirements would become clear from that.
Now question is what's that 'normal distribution' formally means. Is it just anything which looks like "more to the center, less to the borders" or distribution should actually be on average some given curve? Some statistical properties?
If just "more to the center" is the case, does 'triangle' distribution fit? You can derive precise succession of such integer distributions so that number of items of each cost is some function you can calculate. Or you can pick actually normal distribution so that there's single item on borders and total number of items is what you need, then cast remaining items rendomly (according to some remainder average distribution maybe).

[kumaresh_ana]

I am unable to explain better than this. Yes, triangle distribution can also be used. But, the problem is : I cannot figure out how to arrive at figures. Can you layout a pseudocode or an algorithm so that I can better understand what you say?
I cant do floating point arthmetics.

[RoboTact]

I am unable to explain better than this. Yes, triangle distribution can also be used. But, the problem is : I cannot figure out how to arrive at figures. Can you layout a pseudocode or an algorithm so that I can better understand what you say?
I cant do floating point arthmetics.What do you mean by you not able to do pointer arithmetic? Is it just that you mean that you want answer to be in integer values or that floating point operations don't present on target platform?

What you need is dithering. You need to approximate your function by integer values. Target function for dithering is number of items vs. integral. So you need a way to estimate if given integer number of placed items is more or less then integral of target function. So it calls for floating point arithmetic, but for simple function such as slope you can do without that.
http://en.wikipedia.org/wiki/Dithering

[kumaresh_ana]

I cannot do floatingpoint arthmetic because the target platform does not support it.

[kumaresh_ana]

Let X = 2 ^ n. Then I will be able to distribute X precisely as I stated using Binomial Distribution [ (1 + 1 ) ^ n expansion ].
If B = (n + 1) * (2 ^ n2) , where n2 is an integer, then I can redistibute the distribution by scaling the existing distribution of X by 2 ^ n2, ie., I will scale each number in the distribution by 2 ^ n2.

The problem that I face now is "what if the B does not obey the equation?", "What if n2 is negative?"

Now calculate the total cost. "What if total cost > A * N?"

[RoboTact]

Did you get the idea of dithering?

[kumaresh_ana]

I get what is dethiring but I do not know how to apply it. I mean where I can get a 2D array to work on ( as dithering is used on images )?

[RoboTact]

2D is just specific case, that article is not general enough. I'll try to put it in my words.

You have a function f(x), where x is element of some set, for example 2D point or integer value in [1,N]. You try to approximate value of f(x) using values in set S (for example, positive integers), whereas f(x) itself may be real number. Your function is s(x) with values in S. So you move by domain so that at certain point you already set values on some part of domain, Ls is sum of values you already set and Lf is sum of values of function f(x) in those points. When you set value h of next point x, you try minimize |(h+Ls) - (f(x)+Lf)| instead of independant |h-f(x)|.

In your case you move along the axis of costs, I'd move from sides to center. All you need is to find a way to minimize value |(h+Ls) - (f(x)+Lf)| where f(x) and Lf are non necessarily integer. Use some algebra to construct integer minimization function.

[kumaresh_ana]

Yes, I get you now.

f(x) -> normal curve or its equivalent.

But I dont have a function like f(x) which will me give me the ideal values ( because the target do not support floating point arithmetic ).

[RoboTact]

Yes, I get you now.

f(x) -> normal curve or its equivalent.

But I dont have a function like f(x) which will me give me the ideal values ( because the target do not support floating point arithmetic ).You don't need to calculate it in order to find optimal h in that minimization problem. You need to find f(x) such that you can still solve minimization problem and at the same time sum of all f(x) must be equal to total integer number of items.

[kumaresh_ana]

Yes, I get it.