Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Interesting question! :)</p> <p>So if we have n cards and m vendors, the brute force approach might have to check up to n^m combinations, right (a bit less since not each vendor has each card, but I guess that doesn't really matter in the grand scheme of things ;). </p> <p>Let's for a second assume each vendor has each card and then see later-on how things change if they don't.</p> <ol> <li>find the cheapest one-vendor solution.</li> <li>order the cards by price, find the most expensive card that's cheaper at another vendor.</li> <li>for all cards from vendor 1, move them to vendor 2 if they're cheaper there. </li> <li>if having added vendor 2 doesn't make the order cheaper, undo and terminate, otherwise repeat from step 2</li> </ol> <p>So if one vendor doesn't have all cards, you have to start with a multi-vendor situation. For each vendor, you might start by buying all cards that exist there, then apply the algorithm to the remaining cards. </p> <p>Obviously, you may not be able to exploit all subtleties in the pricing with this method. But if we assume that a large portion of the price differences is made up by individual high-price cards, I think you can find a reasonable solution with this way.</p> <hr> <p>Ok after writing all this I realized, the n^m assumption is actually wrong. Once you have chosen a set of vendors to buy from, you can simply choose the cheapest vendor for each card. This is a great advantage because the individual choices of where to buy each card don't interfere with each other. </p> <p>What does this mean for our problem? From the first look of it, it means that the selection of dealers is the problem (in terms of computational complexity), not the individual allocation of your buying choices. So instead of n^m, you got 2^m possible configurations in the worst case. So what we need is a heuristic for choosing vendors rather than choosing individual cards. Which might make the heuristic from above actually even more justifiable.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow to find Best Price for a Deck of Collectible Cards?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNicolas78
    1. USNicolas78
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI was thinking something similar, but I like the way you explained it. Only 2^m? That isn't so bad.
      singulars
      1. PO
      1. USJim McKeeth
    2. COThe other problem with your attack
      singulars
      1. PO
      1. USRisser
    3. COThe problem with your stated attack is that it's possible that buying all possible cards from vendor 2 may be more expensive, but buying a few cheaper cards may be less expensive. For example, say vendor 2 has a sale on cards starting with the letter A, but is more expensive on everything else. It may be cheaper to buy A cards from vendor 2, but also including the other cards pushes it back up over the cost of vendor 1. That's really the problem. Any combination of cards from a vendor has the potential to be cheaper than the same set from another vendor.
      singulars
      1. PO
      1. USRisser
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload