Skip to analysis
This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!
In a certain shop, each kind of product has an integer price. For example, the price of a flower is 2 zorkmids (z) and the price of a vase is 5z. In order to attract more customers, the shop introduces some special offers.
A special offer consists of one or more product items together for a reduced price, also an integer. Examples:
- three flowers for 5z instead of 6z, or
- two vases together with one flower for 10z instead of 12z.
Write a program that calculates the price a customer has to pay for a purchase, making optimal use of the special offers to make the price as low as possible. You are not allowed to add items, even if that would lower the price.
For the prices and offers given above, the (lowest) price for three flowers and two vases is 14z: two vases and one flower for the reduced price of 10z and two flowers for the regular price of 4z.
PROGRAM NAME: shopping
INPUT FORMAT
The input file has a set of offers followed by a purchase.
| Line 1: | s, the number of special offers, (0 <= s <= 99). |
| Line 2..s+1: | Each line describes an offer using several integers. The first integer is n (1 <= n <= 5), the number of products that are offered. The subsequent n pairs of integers c and k indicate that k items (1 <= k <= 5) with product code c (1 <= c <= 999) are part of the offer. The last number p on the line stands for the reduced price (1 <= p <= 9999). The reduced price of an offer is less than the sum of the regular prices. |
| Line s+2: | The first line contains the number b (0 <= b <= 5) of different kinds of products to be purchased. |
| Line s+3..s+b+2: | Each of the subsequent b lines contains three values: c, k, and p. The value c is the (unique) product code (1 <= c <= 999). The value k indicates how many items of this product are to be purchased (1 <= k <= 5). The value p is the regular price per item (1 <= p <= 999). At most 5*5=25 items can be in the basket. |
SAMPLE INPUT (file shopping.in)
2 1 7 3 5 2 7 1 8 2 10 2 7 3 2 8 2 5
OUTPUT FORMAT
A single line with one integer: the lowest possible price to be paid for the purchases.
SAMPLE OUTPUT (file shopping.out)
14
CODE
Java
C++
Pascal
ANALYSIS
Hal Burch
This is a shortest path problem. The goal is to find the shortest path from an empty basket to a basket containing the requested objects. Thus, Dijkstra’s algorithm can be used.
The nodes in the graph correspond to baskets and the edges correspond to offers (purchasing a single item can be considered a degenerate offer). The length of an edge is the cost of the offer. For each item type, there can be between 0 and 5 inclusive objects of that type in the basket, for a total of 6^5 = 7,776 possible baskets.
#include <stdio.h>
#include <string.h>
/* maximum number of offers */
/* 100 offers + 5 degenerate offers */
#define MAXO 105
typedef struct OFFER_T
{
int nitem; /* number of items in the offer */
int itemid[5]; /* item's id */
int itemamt[5]; /* item's amount */
int cost; /* the cost of this offer */
} offer_t;
offer_t offers[MAXO];
int noffer;
/* the cost of each basket type */
int cost[7776];
/* the item statistics */
int itemid[5]; /* the id */
int itemcst[5]; /* the cost of buying just 1 */
int nitem;
/* heap used by Dijkstra's algorithm */
int heap[7776];
int hsize;
int hloc[7776]; /* location of baskets within the heap */
/* debugging routine */
void check_heap(void)
{ /* ensure heap order is maintained */
int lv;
return;
for (lv = 1; lv < hsize; lv++)
{
if (cost[heap[lv]] < cost[heap[(lv-1)/2]])
{
fprintf (stderr, "HEAP ERROR!\n");
return;
}
}
}
/* delete the minimum element in the heap */
void delete_min(void)
{
int loc, val;
int p, t;
/* take last item from the heap */
loc = heap[--hsize];
val = cost[loc];
/* p is the current position of item (loc,val) in the heap */
/* the item isn't actually there, but that's where we're
considering putting it */
p = 0;
while (2*p+1 < hsize)
{ /* while one child is less than the last item,
move the lesser child up */
t = 2*p+1;
/* pick lesser child */
if (t+1 < hsize && cost[heap[t+1]] < cost[heap[t]]) t++;
if (cost[heap[t]] < val)
{ /* if child is less than last item, move it up */
heap[p] = heap[t];
hloc[heap[p]] = p;
p = t;
} else break;
}
/* put the last item back into the heap */
heap[p] = loc;
hloc[loc] = p;
check_heap();
}
/* we decreased the value corresponding to basket loc */
/* alter heap to maintain heap order */
void update(int loc)
{
int val;
int p, t;
val = cost[loc];
p = hloc[loc];
while (p > 0) /* while it's not at the root */
{
t = (p-1)/2; /* t = parent of node */
if (cost[heap[t]] > val)
{ /* parent is higher cost than us, swap */
heap[p] = heap[t];
hloc[heap[p]] = p;
p = t;
} else break;
}
/* put basket back into heap */
heap[p] = loc;
hloc[loc] = p;
check_heap();
}
/* add this element into the heap */
void add_heap(int loc)
{
if (hloc[loc] == -1)
{ /* if it's not in the heap */
/* add it to the end (same as provisionally setting it's value
to infinity) */
heap[hsize++] = loc;
hloc[loc] = hsize-1;
}
/* set to correct value */
update(loc);
}
/* given an id, calculate the index of it */
int find_item(int id)
{
if (itemid[0] == id) return 0;
if (itemid[1] == id) return 1;
if (itemid[2] == id) return 2;
if (itemid[3] == id) return 3;
if (itemid[4] == id) return 4;
return -1;
}
/* encoding constants 6^0, 6^1, 6^2, ..., 6^5 */
const int mask[5] = {1, 6, 36, 216, 1296};
void find_cost(void)
{
int p;
int cst;
int lv, lv2;
int amt;
offer_t *o;
int i;
int t;
/* initialize costs to be infinity */
for (lv = 0; lv < 7776; lv++) cost[lv] = 999*25+1;
/* offer not in heap yet */
for (lv = 0; lv < 7776; lv++) hloc[lv] = -1;
/* add empty baset */
cost[0] = 0;
add_heap(0);
while (hsize)
{
/* take minimum basket not checked yet */
p = heap[0];
cst = cost[p];
/* delete it from the heap */
delete_min();
/* try adding each offer to it */
for (lv = 0; lv < noffer; lv++)
{
o = &offers[lv];
t = p; /* the index of the new heap */
for (lv2 = 0; lv2 < o->nitem; lv2++)
{
i = o->itemid[lv2];
/* amt = amt of item lv2 already in basket */
amt = (t / mask[i]) % 6;
if (amt + o->itemamt[lv2] <= 5)
t += mask[i] * o->itemamt[lv2];
else
{ /* if we get more than 5 items in the basket,
this is an illegal move */
t = 0; /* ensures we will ignore it, since cost[0] = 0 */
break;
}
}
if (cost[t] > cst + o->cost)
{ /* we found a better way to get this basket */
/* update the cost */
cost[t] = cst + o->cost;
add_heap(t); /* add, if necessary, and reheap */
}
}
}
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2; /* loop variable */
int amt[5]; /* goal amounts of each type */
int a; /* temporary variable */
if ((fin = fopen("shopping.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("shopping.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &noffer);
/* read offers */
for (lv = 0; lv < noffer; lv++)
{
fscanf (fin, "%d", &offers[lv].nitem);
for (lv2 = 0; lv2 < offers[lv].nitem; lv2++)
fscanf (fin, "%d %d", &offers[lv].itemid[lv2], &offers[lv].itemamt[lv2]);
fscanf (fin, "%d", &offers[lv].cost);
}
/* read item's information */
fscanf (fin, "%d", &nitem);
for (lv = 0; lv < nitem; lv++)
fscanf (fin, "%d %d %d", &itemid[lv], &amt[lv], &cost[lv]);
/* fill in rest of items will illegal data, if necessary */
for (lv = nitem; lv < 5; lv++)
{
itemid[lv] = -1;
amt[lv] = 0;
cost[lv] = 0;
}
/* go through offers */
/* make sure itemid's are of item's in goal basket */
/* translate itemid's into indexes */
for (lv = 0; lv < noffer; lv++)
{
for (lv2 = 0; lv2 < offers[lv].nitem; lv2++)
{
a = find_item(offers[lv].itemid[lv2]);
if (a == -1)
{ /* offer contains an item which isn't in goal basket */
/* delete offer */
/* copy last offer over this one */
memcpy (&offers[lv], &offers[noffer-1], sizeof(offer_t));
noffer--;
/* make sure we check this one again */
lv--;
break;
}
else
offers[lv].itemid[lv2] = a; /* translate id to index */
}
}
/* add in the degenerate offers of buying single items 8/
for (lv = 0; lv < nitem; lv++)
{
offers[noffer].nitem = 1;
offers[noffer].cost = cost[lv];
offers[noffer].itemamt[0] = 1;
offers[noffer].itemid[0] = lv;
noffer++;
}
/* find the cost for all baskets */
find_cost();
/* calculate index of goal basket */
a = 0;
for (lv = 0; lv < 5; lv++)
a += amt[lv] * mask[lv];
/* output answer */
fprintf (fout, "%i\n", cost[a]);
return 0;
}
Slavi Marinov
This problem can be solved using dynamic programming. This way is easier to code, and for the test cases it runs for much less than 0.1 seconds.
We keep a five dimensional array sol (it’s not that much, because its size is only 5*5*5*5*5*sizeof(special_offer).) Each configuration of the dimensions sol[a][b][c][d][e] corresponds to having a products from the first kind, b products from the second kind, c from the third, etc.
Basically, the DP forumla is the following : sol[a][b][c][d][e]= min (a*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5], so[k].price+ sol[a-so[k].prod[1].items] [b-so[k].prod[2].items] [c-so[k].prod[3].items] [d-so[k].prod[4].items] [e-so[k].prod[5].items] ) where k changes from 1 to the number of special offers. Or, in other words, for each field of the array we check which is better :
* Not to use any special offer * To use some special offer
It’s very similliar to the knapsack problem. The complexity of this algorithm is O(5*5*5*5*5*100)=O(312,500), which is quite acceptable.
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("shopping.in");
ofstream fout("shopping.out");
struct special_offer {
int n;
int price; // the price of that special offer
struct product { // for each product we have to keep :
int id; // the id of the product
int items; // how many items it includes
} prod[6];
} so[100]; // here the special offers are kept
int code[1000], /* Each code is 'hashed' from its real value
to a smaller index. Example :
If in the input we have code 111, 934, 55,
1, 66 we code them as 1,2,3,4,5. That is
kept in code[1000];
*/
price[6], // the price of each product
many[6]; // how many of each product are to be bought
int s, // the number of special offers
b; // the number of different kinds of products to be bought
int sol[6][6][6][6][6]; // here we keep the price of each configuration
void init() { // reads the input
fin>>s;
for (int i=1;i<=s;i++) {
fin>>so[i].n;
for (int j=1;j<=so[i].n;j++)
fin>>so[i].prod[j].id>>so[i].prod[j].items;
fin>>so[i].price;
}
fin>>b;
for (int i=1;i<=b;i++) {
int tmp;
fin>>tmp;
code[tmp]=i; // here we convert the code to an id from 1..5
fin>>many[i];
fin>>price[i];
}
}
void solve() { // the procedure that solves the problem
for (int a=0;a<=many[1];a++)
for (int b=0;b<=many[2];b++)
for (int c=0;c<=many[3];c++)
for (int d=0;d<=many[4];d++)
for (int e=0;e<=many[5];e++)
if ((a!=0)||(b!=0)||(c!=0)||(d!=0)||(e!=0)) {
int min=a*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5];
/* in min we keep the lowest price at which we can buy a items
from the 1st type, +b from the 2nd+c of the 3rd... e from the
5th */
for (int k=1;k<=s;k++) { // for each special offer
int can=1,hm[6];
memset(&hm,0,sizeof(hm));
for (int l=1;l<=so[k].n;l++)
hm[code[so[k].prod[l].id]]=so[k].prod[l].items;
if ((hm[1]>a)||(hm[2]>b)||(hm[3]>c)||(hm[4]>d)||(hm[5]>e))
can=0;// we check if it is possible to use that offer
if (can) { // if possible-> check if it is better
// than the current min
int pr=so[k].price+sol[a-hm[1]][b-hm[2]][c-hm[3]]
[d-hm[4]][e-hm[5]];
/* Those which are not included in the special offer */
if (pr<min) min=pr;
}
}
sol[a][b][c][d][e]=min;
}
}
int main() {
memset(&so,0,sizeof(so));
init();
solve();
fout<<sol[many[1]][many[2]][many[3]][many[4]][many[5]]<<endl;
return 0;
}
Back to top