CONSTRAINT SATISFACTION AND COMBINATORIAL OPTIMISATION
Open Examination
/*
Penny Pincher is an economics student with a tight budget and a small refrigerator. To save money she has already planned all her meals in advance and now would like you to write a program that can solve the difficult problem of planning all her shopping in advance.
First let us consider a particular case of the problem. She needs three food products - A, B, C and D - all of which require refrigeration. She is planning her shopping for 4 weeks and has no food at the start of this period. Each food product is available in packages of different sizes, always a whole number of units. For each week she knows how may units of product are needed; this is always a whole number of units, possibly zero. She also knows the capacity of her refrigerator in terms of number of units, which is also a whole number.
She goes shopping each week and puts all the food products she buys into her refrigerator, which already holds unused food products from the previous week. At this point the refrigeraor must hold enough of each product to meet her planned usage for the forthcoming week. All food products that are unused at the end of the week remain in the refrigerator; Penny discards nothing.
The total amount of food in the refrigerator cannot exceed the capacity of the refrigerator. The food packages are elastic; the amount of space they consume is equal to the amount of food product. Thus, when half the package is used up it consumes half the space.
Input:
refrigerator capacity,
amount of each product needed each week,
for each product a list of the sizes in which it is available.
We shall assume that for each product the list of sizes is consistent in that if the product is available in n units then it is available in all multiples of n since one could purchase multiple packages of size n.