Problem: Bob’s Sale

The problem is NP-complete for the general case. This can be shown via a reduction of 3-partition (which is a still strong NP-complete version of bin packing).

Let w₁, …, w_n be the weights of objects of the 3-partition instance, let b be the bin size, and k = n/3 the number of bins that are allowed to be filled. Hence, there is a 3-partition if objects can be partitioned such that there are exactly 3 objects per bin.

For the reduction, we set N=kb and each bin is represented by b price labels of the same price (think of P_i increasing every bth label). Let t_i, 1≤i≤k, be the price of the labels corresponding to the ith bin.
For each w_i we have one product S_j of quantity w_i + 1 (lets call this the root product of w_i) and another w_i – 1 products of quantity 1 which are required to be cheaper than S_j (call these the leave products).

For t_i = (2b + 1)ⁱ, 1≤i≤k, there is a 3-partition if and only if Bob can sell for 2bΣ_1≤i≤k t_i:

• If there is a solution for 3-partition, then all the b products corresponding to objects w_i, w_j, w_l that are assigned to the same bin can be labeled with the same price without violating the restrictions.
  Thus, the solution has cost 2bΣ_1≤i≤k t_i (since the total quantity of products with price t_i is 2b).
• Consider an optimal solution of Bob’s Sale.
  First observe that in any solution were more than 3 root products share the same price label, for each such root product that is “too much” there is a cheaper price tag which sticks on less than 3 root products. This is worse than any solution were there are exactly 3 root products per price label (if existent).
  Now there can still be a solution of Bob’s Sale with 3 root labels per price, but their leave products do not wear the same price labels (the bins sort of flow over).
  Say the most expensive price label tags a root product of w_i which has a cheaper tagged leave product. This implies that the 3 root labels w_i, w_j, w_l tagged with the most expensive price do not add up to b. Hence, the total cost of products tagged with this price is at least 2b+1.
  Hence, such a solution has cost t_k(2b+1) + some other assignment cost. Since the optimal cost for an existent 3-partition is 2bΣ_1≤i≤k t_i , we have to show that the just considered case is worse. This is the case if t_k > 2b Σ_1≤i≤k-1 t_i (note that it’s k-1 in the sum now). Setting t_i = (2b + 1)ⁱ, 1≤i≤k, this is the case. This also holds if not the most expensive price tag is the “bad” one, but any other.

So, this is the destructive part 😉 However, if the number of different price tags is a constant, you can use dynamic programming to solve it in polynomial time.