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.


Need Your Help

Intersection in CSS3

css css3

Is it possible to make a "hole" in an element (div, span) like this using CSS. I know I can do it with a transparent image but I'm just curious to know if it's possible in CSS.

Mono Playback of Mp3s in Python OR C++

c++ python audio mp3

Im coding a music player in python using pyqt and I wanted it to feature mono playback of mp3 files.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.