# Will this algorithm for a variation on the knapsack work?

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

## Answers

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.