0

I'm writing an FPTAS algorithm for Knapsack problem, and found out that I need to implement dynamic programming by profit for that. I have found many resources for dynnamic programming by weight (O(n * W), n - number of items, W - max capacity), but very little for profit based (O(n^2 * C), n - number of items, C highest profit from one item).

I have found only one source with pseudo code here (it's in Polish, but you can see code and functions starting at page 7): http://www.asdpb.republika.pl/wyk78.pdf

My code:

F = new int[items.Count + 1, (Pmax * items.Count) + 1];
int y;
int k;
int profit = 0;
for (k = 0; k < items.Count; k++)
{
    for (y = 0; y < (Pmax * items.Count); y++)
    {
        if (y == 0 && k >= 1)
            F[k, y] = 0;
        else if (y >= 1 && k == 0)
            F[k, y] = int.MaxValue;
        else if (k >= 1 && y >= 1)
        {
            if (y - items[k].profit < 0)
                F[k, y] = (int)Math.Min(F[k - 1, y], int.MaxValue);
            else
                F[k, y] = (int)Math.Min(F[k - 1, y], F[k - 1, y -    items[k].profit] + items[k].weight);    
        }
    }
}

y = 0;
do
{
    y++;
    for (k = 1; k < items.Count; k++)
    {
        if (y - items[k].profit < 0)
            F[k, y] = F[k - 1, y];
        else if (F[k - 1, y - items[k].profit] == int.MaxValue)
            F[k, y] = F[k - 1, y];
        else
            F[k, y] = (int)Math.Min(F[k - 1, y], F[k - 1, y - items[k].profit] + items[k].weight);
        if(F[items.Count,y] <= maxCapacity)
           profit = y;
    }
} while (y < Pmax * items.Count);

I'm using sample data from website linked before:

n = 3
profits = [2,3,1]
weights = [1,3,3]
capacity = 5

But it returns profit = 9 and entirely diffrent table F. What's wrong with my code? Are there any other good sources for this?

Alternatively I can implement PTAS algorithm but I could not find any good sources either.

4
  • could you explain the question , with an example of what you are trying to achieve ? Jan 18, 2015 at 11:45
  • If I understand correctly is it that you have C amount of money and n items each has a cost/weight and profit associated and you want to buy things to maximize the profit ? Am I correct ? Jan 18, 2015 at 11:49
  • @sasha C is highest value from all items (Pmax in code) I need to create table with numbers of columns = n * C and number of rows = n. The values in table are weights. For example row 2 and column 3 shows maximum two first items (or less) with profit equal to 3, so if not possible it's infinity (int.MaxValue). Profit here is value not value/weight Jan 18, 2015 at 12:08
  • 1
    Please explain what exactly is the semantics of the value in state 'F[a,b]' and what the range of a and b would be. Most likely the FPTAS is attained by first using an exact algorithm but modifiying the instance by rounding it suitably, dependent on e.g. the maximum profit and the number of items.
    – Codor
    Jan 18, 2015 at 16:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.