Random Shopping Algorithm

This is a problem I've ran into a number of times yet have never found a happy solution to. I've coined it the "Random Shopping Algorithm", and the set up is as follows:

Given a certain amount of money and presented with a collection of items, each with a different cost, the algorithm should return a random group of items to purchase whose total is the amount of money given.

Just pick items at random until the money is exhausted does not work, as it won't select "many cheap items" as often as it should. For example, consider the case with $20 and two items: A, costing $10; and B, costing $1. There are three possible outcomes:

1. Buy 20 As
2. Buy 10 A and 1 Bs
3. Buy 2 Bs

The algorithm should come up with these three outcomes with equal probability. If you simply select the item to purchase with equal weighting, chances are you will end up with outcome 2 more often than option 1, and rarely see option 3 at all.

Because of this, I tried varying the probably at which each item is selected, hoping to find a point where all three outcomes had an equal chance. That this doesn't work is probably not too hard to see, but the detailed results are shown in fig 1. This means that a simple re-weighting of the items based on their cost is not sufficient, and perhaps the weighting will have to chance as items are purchased.

The brute force method of accomplishing this is to create a comprehensive list of all possible purchase-sets, and then merely select an item at random. This would obviously be very slow and become slower as more items are added, so is not practical for the general case. Starting with this concept may however be helpful in finding a more efficient algorithm.

On Gratuitous Notions

Welcome

I've created this blog as a place to get whatever thoughts are in my head down on paper, so to speak. I expect the topics to cover a wide spectrum, from controversial issues to game reviews to personal experiences: whatever I feel inclined to write about at the time. Instead of giving myself complete freedom, I'm aiming for weekly posts, but we'll see how it goes :-)

On Abortion

With Sarah Palin joining the republican ticket, abortion's once again become a hot topic. I'm going to attempt to summarise my own stance and describe the arguments from each side.

First of all, I detest the emotive language that has developed around the issue. The terms "pro-life" and "pro-choice" are seeped in derogatory vitriol. Of course the "pro-choice" crowd aren't against life in any general sense, nor are the "pro-life" advocates against people having a general freedom of choice. These terms simply cause anger, further division and defensiveness in both camps, and don't at all help us to find an affective compromise. Unfortunately, such is the nature of language that complicated positions must be striped down to simple terms, so with reluctance I will accept their use.

Any examination of the abortion debate must start with the deceptively simple question, "When does life begin?" How one answers this question almost completely decides where they will fall in any discussion of abortion. The two most common answers are: A) at conception, or B) at birth. Like all controversial issues, it is impossible to prove this central question one way or the other: is life within the womb truly life? Or is the loss of a potential life a tragedy that must be avoided at all costs? I certainly don't have the answers, and personally believe that no one does.

That's the issue from the point of view of the fetus; the other side is of course that of the mother. Most would agree that each woman has the sole right to decide what can and can not happen within her body, but the central question becomes "Is a fetus part of a woman's body?" A rigorous scientific examination of that question would probably be inconclusive, but in this case I think the obvious answer is more than sufficient: anything within a person's body is part of that person.

But, if we decide that a woman the sole person allowed to make choices for within her own body, and that a fetus is alive from the point of conception, are we effectively giving women the right to murder their fetuses? I think we are, and that that is actually alright. It's not unprecedented, either. We give police the right to shoot criminals in certain situations, and soldiers the right to murder those of opposing army and even accept a certain amount of innocent civilian casualties—we might not approve of them, but we certainly don't try the soldiers for murder. And that's not even considering the amount of acceptable murder of animals for food, hunting, or development.

In summary, I do believe that terminating a fetus is ending a life, but that that is acceptable as no one else can say what a woman chooses to do within her own body. Consider the alternative: if abortions where illegal, one small accident—a drunken mistake, forgetting a pill, a weak condom—could leave a woman with the life-long burden of a child. It's a wonderful burden, to be sure, but also a financial and social one. That seems to me a punishment far out of proportion for such a small indiscretion. I know that life isn't always fair, but I thought the goal of a civilization was to create a society of fairness and justice for all.