Author |
Topic: Variable profit knapsack (Read 1657 times) |
|
indiauec
Newbie
vaibhav
Gender: 
Posts: 10
|
 |
Variable profit knapsack
« on: Sep 24th, 2010, 5:10pm » |
 Quote  Modify
|
We are given integers Cx,i Cy,i Cz,i and Px,i Py,i Pz,i > 0 for i=1,2,3
such that
Px,1 < Px,2 < Px,3
Py,1 < Py,2 < Py,3,
and Pz,1 < Pz,2 < Pz,3.
We are also given an integer K.
The values Cx,i and Px,i describe the content of a stack named x. From top to bottom, the stack x contains Cx,1 items each of profit Px,1. Cx,2 items each of profit Px,2. and Cx,3 items each of profit Px,3. The contents of stacks y and z are defined in the same way.
We are allowed to pop K items in total from the three stacks. How can I maximize the total profit?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Variable profit knapsack
« Reply #1 on: Sep 25th, 2010, 2:47pm » |
Quote Modify
|
Take i items from stack x, j items from stack y, and K-i-j items from stack z; maximize over i and j. Quadratic runtime isn't too bad.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
indiauec
Newbie
vaibhav
Gender:
Posts: 10
|
|
Re: Variable profit knapsack
« Reply #2 on: Sep 25th, 2010, 5:58pm » |
Quote Modify
|
P(final) = F1(x,i) + F2(y,j) + F3(z,K-i-j)
where
F1(x,i) is
i * Px,1 when i < Cx,1
(i - Cx,1) * Px,2 + Cx,1 * Px,2 when Cx,1 < i < Cx,2
etc.
This will make it non polynomial wrt number of stacks and number of layers in each stack
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Variable profit knapsack
« Reply #3 on: Jan 28th, 2011, 8:53pm » |
Quote Modify
|
Won't the greedy approach work here? As in start popping from the queue with maximum profit element of the three and when the value changes, compare again and pick max again.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Variable profit knapsack
« Reply #4 on: Jan 29th, 2011, 2:15am » |
Quote Modify
|
on Jan 28th, 2011, 8:53pm, birbal wrote:| Won't the greedy approach work here? |
|
No, because the least valuable items are on the top. So say you have a stack of (100, 1) and two stacks of (3, 2), and K=2. Then the greedy approach would get you a profit of 5, but the best approach would get you 101.
|
| « Last Edit: Jan 29th, 2011, 2:16am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Variable profit knapsack
« Reply #5 on: Jan 29th, 2011, 3:20am » |
Quote Modify
|
on Jan 29th, 2011, 2:15am, towr wrote:
No, because the least valuable items are on the top. So say you have a stack of (100, 1) and two stacks of (3, 2), and K=2. Then the greedy approach would get you a profit of 5, but the best approach would get you 101.
|
|
Ahhh...i see the heck in greedy.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print