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.
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]
}
}
}
}
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.