The Shopping Problem : Let I={i1,i2...ik} be the items on your shopping list. Let S = {s1,s2,....,sm} be the list of stores each store si sells only a subset of the items on your shopping list, and also the cost the items sold by the shops may vary i.e item ij may be sold with different prices in different shops, so let C[i,j] be the cost of item i in store j. Since the shops are located in different places let D[p,q] be the cost of reaching store q from store p. So our aim is to start at home (H) and buy all the items we want and return to home with minimum possible cost. As I mentioned in the previous post this problem is was mentioned in Google Code Jam practice problems, however I did not see many submissions to this problem.
Firstly the problem is NP-hard because if items sold by each of the stores are disjoint and they are singleton sets then we should visit all the stores in the right
order to minimize the total distance traveled, this is nothing by TSP. The following is the dynamic programming formulation for this problem. Let S(V,j) be a optimal solution to buy all the items in set V ending at store j. Then
the following is the DP formulation.
S(V,j) = min { S(V-{k},p) + D[p,j] + C[k,j] } ; k \in V, 1<=p<=m
Final Answer = min { S(I,j) + D[j,Home] } Initialization of the
DP is simple you may want to look at the code below.
Further complexity to the problem can be added by saying that the items are
classified as PerishableP and Non-PerishableN. So when ever you
buy a perishable item you need to go back home to put in the refrigerator. The
above DP formulation can be extended to this easily as follows. Let S(V,j,P)
be the optimal sub problem of shopping all the items in the set V ending
at the store j and having a Perishable item in the shopping cart, on the
same lines S(V,j,N) optimal sub problem of shopping all the items in the
set V ending at store j with NO perishable item in the shopping cart.
Then the following formulation will give the optimal solution.
S(V,j,P) = min {S(V-{k},p,P) + D[p,Home] + D[Home,j] + C[k,j] } or
min {S(V-{k},p,N) + D[p,j] + C[k,j] }
If k is a perishable item
We can write similar formulations for Non-Perishable items also, get the code here implementing
the shopping problem.
1 /*Vamsi Kundeti (vamsi(dot)krishnak(at)gmail*/ 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<assert.h> 6 #include<math.h> 7 #include "List.h" 8 unsigned int **GRAPH; 9 //#define VERBOSE_MODE 1 10 unsigned int item_bits; 11 char **item_names; 12 unsigned int item_subset; 13 /*has a unsigned int indicating 14 *if this shop sells the item or not 15 */ 16 unsigned int *shop_sells; 17 /*dist[i][j] indicates the distance 18 *between i and j*/ 19 double **dist; 20 /*cost[i][j] indicates the cost of 21 *item i in shop j 22 */ 23 double **cost; 24 /*The number of the items*/ 25 unsigned int icount; 26 /*The number of test cases*/ 27 unsigned int tcount; 28 unsigned int caseno; 29 /*The number of shops**/ 30 unsigned int scount; 31 typedef struct _pair_ { 32 int x; 33 int y; 34 }Coor; 35 Coor *shop_coor; 36 void EnumSubSetsBFS(unsigned int n); 37 unsigned int LookUpItem(const char *key){ 38 unsigned int i=0; 39 for(i=0;i<icount;i++){ 40 if(!strcmp(key,item_names[i])){ 41 return i+1; 42 } 43 } 44 /*Ignore this item*/ 45 return 0; 46 } 47 unsigned int gas_price; 48 unsigned int perish; 49 inline char CheckPerish(unsigned int i){ 50 return (perish & (1<<(i)))?1:0; 51 } 52 void ReadInput(void){ 53 unsigned int i,j; 54 unsigned int len; 55 unsigned int icost; 56 char item_buffer[64]; 57 char delim; 58 scanf("%u",&tcount); 59 while(tcount--){ 60 perish=0; 61 scanf("%u %u %u",&icount,&scount,&gas_price); 62 assert(icount && scount); 63 /*Read the items to be bought*/ 64 item_names = (char **) malloc(sizeof(char *)*icount); 65 for(i=0;i<icount;i++){ 66 scanf("%s",&item_buffer); 67 len = strlen(item_buffer); 68 len = (len > 64)?64:len; 69 item_names[i] = (char *) malloc(sizeof(char)*(len+1)); 70 assert(memcpy(item_names[i],item_buffer,(len+1))==item_names[i]); 71 if(len && (item_names[i])[len-1]=='!'){ 72 perish = perish | (1 << (i)); 73 (item_names[i])[len-1]='\0'; 74 } 75 } 76 shop_coor = (Coor *) malloc(sizeof(Coor)*(scount+1)); 77 cost = (double **) malloc(sizeof(double *)*(scount+1)); 78 shop_sells = (unsigned int *)malloc(sizeof(unsigned int)*(scount+1)); 79 shop_coor[0].x = 0.0; 80 shop_coor[0].y = 0.0; 81 for(i=1;i<scount+1;i++){ 82 cost[i] = (double *) malloc(sizeof(double)*icount); 83 scanf("%d %d",&(shop_coor[i].x),&(shop_coor[i].y)); 84 shop_sells[i] = 0; 85 for(j=0;j<icount;j++){ 86 cost[i][j] = 0; 87 } 88 while(1){ 89 scanf(" %[^:]:%u",item_buffer,&icost); 90 if(j=LookUpItem(item_buffer)){ 91 cost[i][j-1] = icost; 92 /*Also set the sells bit_set*/ 93 shop_sells[i] = shop_sells[i] | (1<<(j-1)); 94 } 95 scanf("%c",&delim); 96 if(delim == '\n'){ 97 break; 98 } 99 } 100 } 101 /*Now Compute the distance matrix*/ 102 dist = (double **)malloc(sizeof(double *)*(scount+1)); 103 for(i=0;i<scount+1;i++){ 104 dist[i] = (double *)malloc(sizeof(double)*(scount+1)); 105 for(j=0;j<scount+1;j++){ 106 dist[i][j] = sqrtf((shop_coor[i].x - shop_coor[j].x)* 107 (shop_coor[i].x - shop_coor[j].x) +(shop_coor[i].y - shop_coor[j].y)* 108 (shop_coor[i].y - shop_coor[j].y)); 109 } 110 } 111 #if 0 112 printf("Items..\n"); 113 for(i=0;i<icount;i++){ 114 printf("%s ",item_names[i]); 115 } 116 printf("\n"); 117 printf("Cost Matrix\n"); 118 for(i=0;i<scount+1;i++){ 119 printf("(%d,%d)",shop_coor[i].x,shop_coor[i].y); 120 for(j=0;j<icount;j++){ 121 if(cost[i][j]){ 122 printf(" %s[%c]:%lf",item_names[j],((CheckPerish(j))?'P':'U'),cost[i][j]); 123 } 124 } 125 printf("\n"); 126 } 127 printf("\n"); 128 #endif 129 /*Make the call to the dynamic programming routine*/ 130 EnumSubSetsBFS(icount); 131 132 /*Freeup the stuff*/ 133 for(i=0;i<icount;i++){ 134 free(item_names[i]); 135 } 136 free(item_names); 137 free(shop_coor); 138 free(shop_sells); 139 for(i=1;i<scount+1;i++){ 140 free(cost[i]); 141 } 142 free(cost); 143 for(i=0;i<scount+1;i++){ 144 free(dist[i]); 145 } 146 free(dist); 147 } 148 } 149 150 void CreateGraph(unsigned int *n){ 151 unsigned int i,j; 152 printf("Enter the Graph Size\n"); 153 scanf("%u",n); 154 printf("Enter the weighted graph\n"); 155 GRAPH = (unsigned int **) malloc(sizeof(unsigned int *)*(*n)); 156 for(i=0;i<*n;i++){ 157 GRAPH[i] = (unsigned int *) malloc(sizeof(unsigned int)*(*n)); 158 for(j=0;j<*n;j++){ 159 scanf("%u",&(GRAPH[i][j])); 160 } 161 } 162 } 163 164 165 unsigned int subset_count=0; 166 int main(){ 167 /*Create the Graph*/ 168 unsigned int n; 169 caseno=0; 170 ReadInput(); 171 //EnumSubSetsBFS(n); 172 173 } 174 /*Returns the new tail of the list*/ 175 inline List* ListAppend(List **tail,void *_data){ 176 List *new_node = (List *)malloc(sizeof(new_node)*1); 177 assert(new_node); 178 if(!(*tail)){ 179 (*tail) = new_node; 180 (*tail)->_data = _data; 181 (*tail)->next = NULL; 182 return *tail; 183 } 184 new_node->_data = _data; 185 new_node->next = NULL; 186 (*tail)->next = new_node; 187 return new_node; 188 } 189 typedef struct _subset_{ 190 /*if i^th bit is set then subset has i^th 191 *element*/ 192 unsigned int ebits; 193 unsigned int max; /*Maximum element in the subset*/ 194 unsigned int size; /*Size of subset*/ 195 /*Pointer to the sub-problem S({},i,0) S({},i,1)*/ 196 void *sub_problem; 197 }SubSet; 198 199 /*Enumerate the Subset using BFS, n is 200 *the set size [1,2...n] */ 201 void EnumSubSetsBFS(unsigned int n){ 202 unsigned int check_sub_set,k,i,j; 203 unsigned int current_level = 0; 204 List *bfs_list = NULL; 205 List *tail = NULL; List *free_node,*ptr; 206 SubSet *sub_set,*new_sub_set; 207 SubSet *one_sets = NULL; 208 209 one_sets = (SubSet *)malloc(sizeof(SubSet)*icount); 210 assert(one_sets); 211 /*Add the 1-subsets i=items*/ 212 for(i=0;i<icount;i++){ 213 one_sets[i].ebits = 0; one_sets[i].ebits |= (1<<i); 214 one_sets[i].max = i; one_sets[i].size = 1; 215 /****SUBPROBLEM SPECIFIC*****/ 216 one_sets[i].sub_problem = (double **)malloc(sizeof(double *)*2); 217 /* Perishable S({i},X,0) */ 218 ((double **)one_sets[i].sub_problem)[0] = (double *) malloc(sizeof(double)*(scount+1)); 219 /* Unperishable S({i},X,1) */ 220 ((double **)one_sets[i].sub_problem)[1] = (double *) malloc(sizeof(double)*(scount+1)); 221 double **sub_problem_i = (double **)one_sets[i].sub_problem; 222 223 /*j is the shop*/ 224 for(j=1;j<scount+1;j++){ 225 /*if item i can be bought at shop j 226 *depending on perishable or not initialize sub_problem[0] 227 *sub_problem[1] 228 */ 229 sub_problem_i[0][j] = HUGE_VAL; sub_problem_i[1][j] = HUGE_VAL; 230 if(shop_sells[j]&(1<<i)){ 231 if(CheckPerish(i)){ 232 sub_problem_i[0][j] = dist[0][j]*(gas_price) + cost[j][i]; 233 }else{ 234 sub_problem_i[1][j] = dist[0][j]*(gas_price) + cost[j][i]; 235 } 236 } 237 #ifdef VERBOSE_MODE 238 printf("S({%u},%u,0) = %lf\n",i+1,j+1,sub_problem_i[0][j]); 239 printf("S({%u},%u,1) = %lf\n",i+1,j+1,sub_problem_i[1][j]); 240 #endif 241 } 242 /*****************************/ 243 if(!tail){ 244 ListAppend(&bfs_list,(void *)&(one_sets[i])); 245 tail = bfs_list; 246 continue; 247 } 248 tail = ListAppend(&tail,(void *)&(one_sets[i])); 249 } 250 251 252 253 /*Now do the BFS*/ 254 while(bfs_list){ 255 sub_set = (SubSet *)bfs_list->_data; 256 free_node = bfs_list; 257 bfs_list=bfs_list->next; 258 subset_count++; 259 assert(sub_set->max < icount); 260 for(i=((sub_set->max)+1);i<icount;i++){ 261 new_sub_set = (SubSet *) malloc(sizeof(SubSet)*1); 262 new_sub_set->size = (sub_set->size)+1; 263 new_sub_set->max = i; 264 new_sub_set->ebits = (sub_set->ebits | (1<<i)); 265 /*This subset enumeration is critical to Subset based D.P*/ 266 267 /*****<begin>**SUBPROBLEM SPECIFIC******/ 268 /* S(X,j) = min_k {S(X-k,k) + d[k][j]}*/ 269 ptr = free_node; 270 double current_min = HUGE_VAL; 271 double **new_sub_problem; 272 double **sub_problem; double local_min; 273 double local_min_perish,local_min_unperish; 274 unsigned int k1,perish,shop1; 275 List *ptr_prev; 276 277 new_sub_set->sub_problem = (double **) malloc(sizeof(double *)*2); 278 ((double **)new_sub_set->sub_problem)[0] = (double *) malloc(sizeof(double)*(scount+1)); 279 ((double **)new_sub_set->sub_problem)[1] = (double *) malloc(sizeof(double)*(scount+1)); 280 new_sub_problem = (double **)new_sub_set->sub_problem; 281 282 for(perish=0;perish<=1;perish++){ 283 for(j=1;j<scount+1;j++){ 284 /*Objective here is to fill up S({new_sub_set},j,0) 285 *and S({new_sub_set},j,1)*/ 286 ptr = free_node; 287 current_min = HUGE_VAL; 288 for(k=1;k<=new_sub_set->size;k++){ 289 do{ 290 check_sub_set = ((SubSet *)ptr->_data)->ebits; 291 check_sub_set ^= new_sub_set->ebits; 292 k1 = (int)log2(check_sub_set); 293 ptr_prev = ptr; 294 ptr=ptr->next; 295 }while(check_sub_set & (check_sub_set-1)); 296 297 /*j is the shop and k1 is the item which you want 298 *to buy at this shop, depending on 299 *perishablity create the value of current min. 300 */ 301 if(!(shop_sells[j] & check_sub_set)){ 302 continue; /*The shop don't sell this*/ 303 } 304 sub_problem = (double **) 305 ((SubSet *)ptr_prev->_data)->sub_problem; 306 /*item k1 is sold by shop j*/ 307 local_min = HUGE_VAL; 308 if((perish && !CheckPerish(k1)) 309 || (!perish && CheckPerish(k1))){ 310 for(shop1=1;shop1<scount+1;shop1++){ 311 /*S{{new_sub_set}-{k1},shop1} + 312 d(shop1,h) + d(h,j) + c[k1][j]*/ 313 if(j != shop1 || perish){ 314 local_min_perish = 315 sub_problem[0][shop1] + 316 (dist[shop1][0] + dist[0][j])* 317 (gas_price) + cost[j][k1]; 318 }else if(!perish){ 319 local_min_perish = sub_problem[0][shop1] + 320 cost[j][k1]; 321 } 322 local_min_unperish = sub_problem[1][shop1] + 323 (dist[shop1][j])*(gas_price) + cost[j][k1]; 324 local_min_perish = 325 (local_min_perish < local_min_unperish)? 326 local_min_perish:local_min_unperish; 327 328 if(local_min_perish < local_min){ 329 local_min = local_min_perish; 330 } 331 } 332 } 333 if(local_min < current_min){ 334 current_min = local_min; 335 } 336 } 337 new_sub_problem[perish][j] = current_min; 338 } 339 } 340 341 #ifdef VERBOSE_MODE 342 printf("Printing S(V,i) size=%u \n",sub_set->size); 343 /*Print SubSet*/ 344 unsigned int i1; 345 for(i1=1;i1<scount+1;i1++){ 346 printf("S({"); 347 unsigned int j1; 348 /*Get the elements back*/ 349 check_sub_set = new_sub_set->ebits; 350 for(j1=0;j1<icount;j1++){ 351 if(check_sub_set & (1<<j1)){ 352 printf(" %u ",j1+1); 353 } 354 } 355 printf("},%u,0)=%lf\n",i1+1,((double **)(new_sub_set->sub_problem))[0][i1]); 356 printf("S({ABOVE},%u,1)=%lf\n",i1+1,((double **)(new_sub_set->sub_problem))[1][i1]); 357 } 358 #endif 359 360 /**********<END>****************/ 361 tail = ListAppend(&tail,(void *)new_sub_set); 362 } 363 364 if(sub_set->size == icount){ 365 double final_answer=HUGE_VAL; 366 double local_min; double **sub_problem; 367 sub_problem = (double **) sub_set->sub_problem; 368 for(j=1;j<scount+1;j++){ 369 local_min = (sub_problem[0][j]<sub_problem[1][j])? 370 sub_problem[0][j]:sub_problem[1][j]; 371 local_min += (dist[j][0])*(gas_price); 372 if(local_min < final_answer){ 373 final_answer = local_min; 374 } 375 } 376 printf("Case #%u: %0.7lf\n",++caseno,final_answer); 377 } 378 379 if(!(sub_set >= one_sets && sub_set <= &(one_sets[icount-1]))){ 380 free(((double **)sub_set->sub_problem)[0]); 381 free(((double **)sub_set->sub_problem)[1]); 382 free(sub_set->sub_problem); 383 free(sub_set); 384 } 385 free(free_node); 386 } 387 for(i=0;i<icount;i++){ 388 free(((double **)one_sets[i].sub_problem)[0]); 389 free(((double **)one_sets[i].sub_problem)[1]); 390 free(one_sets[i].sub_problem); 391 } 392 free(one_sets); 393 // printf("SubsetCount=%u\n",subset_count); 394 } 395
No comments:
Post a Comment