Databases
StackOverflow2013
Postsdbo
POHow to find Best Price for a Deck of Collectible Cards?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to find Best Price for a Deck of Collectible Cards?
    primarykey
    data
    text
    <h2>Or <em>The Traveling Salesman plays Magic!</em></h2> <p><em>I think this is a rather interesting algorithmic challenge. Curious if anyone has any good suggestions for solving it, or if it is already solvable in a known way.</em></p> <p><a href="http://TCGPlayer.com/" rel="nofollow noreferrer">TCGPlayer.com</a> sells collectible cards for a variety of games, including <em>Magic the Gathering</em>. Instead of just selling cards from their inventory they are actually a <em>re-seller from multiple vendors</em> (50+). Each vendor has a <strong>different inventory</strong> of cards and a <strong>different price per card</strong>. Each vendor also charges a <strong>flat rate for shipping</strong> (usually). Given all of that, how would one find the best price for a deck of cards (say 40 - 100 cards)?</p> <p>Just finding the best price for each card doesn't work because if you order 10 cards from 10 different vendors then you <strong>pay shipping 10 times</strong>, but if you order all 10 from one vendor you only <strong>pay shipping once</strong>. </p> <p>The other night I wrote a simple HTML Scraper (using <a href="http://html-agility-pack.net/?z=codeplex" rel="nofollow noreferrer">HTML Agility Pack</a>) that grabs all the different prices for each card, and then finds all the vendors that carry all the cards in the deck, totals the price of the cards from each vendor and sorts by price. That was really easy. The total prices ended up being near the total median price for all the cards.</p> <p>I did notice that some of the individual cards ended up being much higher than the median price. That raises the question of splitting an order over multiple vendors, but only if enough savings could be made by splitting the order up to cover the additional shipping (each added vendor adds another shipping charge).</p> <p>Logically it seems that the best price will probably only involve a few different vendors, but if <strong>the cards are expensive enough (<a href="http://magic.tcgplayer.com/db/magic_single_card.asp?cn=Jace,%20the%20Mind%20Sculptor" rel="nofollow noreferrer">and some are</a>)</strong> then in theory ordering each card from a different vendor could still result in enough savings to justify all the extra shipping.</p> <p>If you were going to tackle this how would you do it? Pure <strong>brute force</strong> figuring every possible combination of card / vendor combinations? A process that is more likely to be done in my lifetime would seem to involve a <strong>methodical series of estimates</strong> over a fixed number of iterations. I have a couple ideas, but am curious what others might suggest.</p> <p>I am looking more for the algorithm than actual code. I am currently using .NET though, if that makes any difference. </p> <p><img src="https://i.stack.imgur.com/Wap0w.jpg" alt="Jace, the Mind Sculptor"></p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USJim McKeeth
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to find Best Price for a Deck of Collectible Cards?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to find Best Price for a Deck of Collectible Cards?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to find Best Price for a Deck of Collectible Cards?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIsn't this basically the knapsack problem? http://en.wikipedia.org/wiki/Knapsack_problem
      singulars
      1. POHow to find Best Price for a Deck of Collectible Cards?
      1. UStauran
    2. COdefinitely has an NP-complete flavor to it. however, many of those problems have efficient approximations for particular assumptions about the input - that's what I take Jim's question to be about.
      singulars
      1. POHow to find Best Price for a Deck of Collectible Cards?
      1. USNicolas78
    3. CO<joke>You will probably want to assign `Jace.vendor=eBay` by default.</joke>
      singulars
      1. POHow to find Best Price for a Deck of Collectible Cards?
      1. USninjagecko
 

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