Bob's Sale (reordering of pairs with constraints to minimize sum of products)
This is a follow-up on Gero's answer.  The idea is to modify his construction to show strong NP-hardness.

Instead of choosing $t_i=(2b+1)^i$, chose $t_i=i$.  Now, you have to modify the argument that a solution with prize $P=2b\sum_{1\leq i \leq k} t_i$ implies that there exists a 3-partition. 

Take an arbitrary shelf order.  Do the accounting in the following way: distribute $w_i-1$ units of quantity of the root-product to its leaf-products.  Then every product has quantity 2.  By definition of the constraints, this does not shift to a higher price.
After this shifting, the price will be exactly $P$.
If the shifting moved some quantity to a lower prize, the original prize was strictly larger than $P$.

Hence, it is only possible to achieve the claimed prize, if all leaf-products have the same prize as their root-product, which means that there exists a 3-partition.

Citing the result from a SWAT 2010 paper this argument shows that even with unary encoding of the numbers and $k$ different price tags, a running time of $f(k)\cdot n^{O(1)}$ would violate "standard complexity assumptions".
This makes the hinted at dynamic programming with a running time of $n^{O(k)}$ look not so bad.



Also cross-posted to the original stack-overflow question.