Question

I am not sure how much of variation it actually is, but here is the problem:

You are about to set out on a long journey, before you do so you need to pack your bag. You have a selection of N items which you could take along. Each item has a weight and value representing how useful it will be. You will not be able to carry more than than K kilograms. What is the maximum total value of the items you can take with? (You can only have one copy of each item.)

I have created an algorithm that I think will solve the problem using DP, but I am not sure if it will work, it would be great if one of you would take a look at it. Note: it is more like a combination of psuedo code and a algorithm, I am not too sure how to write either.

Assuming k is the max weight. Two arrays: one containing the weight of each item w[] and the other the value v[].

 for i = 0; i<numberOfItems; i++
 {
    value = 0
    k = MaxWeight;
    for(j = i; j<numberOfItems; j++
    {
        if(j = i)
        {
            if(k - w[i] >= 0)
            {
                k = k-w[i]
                value = value + v[i]
            }
        }
        else
        {
            if(k - w[j] >= 0)
            {
                k = k-w[j]
                value = value + v[j]
            }
        }
    }
}
Was it helpful?

Solution

No, your greedy algorithm won't work.

Check this example:

MaxWeight = 12
Items = 4 5 4 4 (each value is 1)

Your algorithm would choose items 1 and 2 (or items 2 and 3, or 3 and 4). Optimal solution is to take items 1, 3 and 4.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top