fork download
copy 
  1. bookCount = 10
  2. shopCount = 10
  3. deliveryCharge = 4
  4.  
  5. '''
  6. cost = [None for i in range(bookCount)]
  7. for m in range(bookCount):
  8.     cost[m] = list(map(int, input().split()))
  9. '''
  10. cost = [[13, 19, 16, 19, 19, 18, 17, 16, 15, 14],
  11.         [18, 13, 17, 14, 15, 16, 15, 17, 18, 17],
  12.         [17, 14, 13, 17, 16, 18, 16, 17, 18, 17],
  13.         [19, 18, 17, 13, 16, 15, 15, 16, 17, 14],
  14.         [16, 14, 17, 18, 13, 16, 15, 16, 17, 16],
  15.         [17, 17, 16, 14, 15, 13, 16, 17, 18, 16],
  16.         [17, 14, 16, 17, 15, 16, 13, 18, 19, 17],
  17.         [17, 16, 15, 14, 17, 16, 15, 13, 15, 15],
  18.         [15, 15, 16, 18, 17, 15, 16, 15, 13, 14],
  19.         [16, 14, 16, 18, 17, 17, 15, 16, 18, 13]]
  20.  
  21.  
  22. def countSetBits(x):
  23.     bits = 0
  24.     while x:
  25.             bits += 1
  26.             x &= x-1
  27.     return bits
  28.  
  29. bestCostSoFar = float('inf')
  30. bestSourcesSoFar = [None for i in range(bookCount)]
  31. for setIndex in range(1, 1 << shopCount):
  32.     totalDeliveryCharge = deliveryCharge * countSetBits(setIndex)
  33.     costForThisSet = 0
  34.     bookSourcesForThisSet = [None for i in range(bookCount)]
  35.     costForThisSet += totalDeliveryCharge
  36.     for bookId in range(bookCount):
  37.         minBookCost = float('inf')
  38.         for shopId in range(shopCount):
  39.             if (1 << shopId) & setIndex:
  40.                 if cost[bookId][shopId] < minBookCost:
  41.                     bookSourcesForThisSet[bookId] = shopId
  42.                     minBookCost = cost[bookId][shopId]
  43.         costForThisSet += minBookCost
  44.     if costForThisSet < bestCostSoFar:
  45.         bestCostSoFar = costForThisSet
  46.         bestSourcesSoFar = bookSourcesForThisSet
  47.  
  48. print(bestCostSoFar)
  49. print(bestSourcesSoFar)
  50.  
Success #stdin #stdout 0.09s 9348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
149
[9, 1, 1, 9, 1, 9, 1, 9, 9, 9]
https://ideone.com/M3IVzU
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!