How to display all included numbers in KnapSack problem?

user_13690322 0
Viewed 210

I have a problem with displaying used numbers. I'm using KnapSack algorithm and I want to display all numbers that I used to get highest value. So there is my code:

static int max(int a, int b)
{
    int c = (a > b) ? a : b;
    Console.WriteLine(c);
    return (a > b) ? a : b;
}

// Returns the maximum value that can 
// be put in a knapsack of capacity W            
int knapSack(int[] r, int[] wt, int n, int W)
{

    if (W < 0)
        return Int32.MinValue;
    if (n < 0 || W == 0)
        return 0;
    int include = r[n] + knapSack(r, wt, n, W - wt[n]);
    int exclude = knapSack(r, wt, n - 1, W);
    int V = max(include, exclude);
    return V;
}

Use:

int[] r = new int[] { 3, 4, 8, 5, 6 };
int[] wt = new int[] { 2, 2, 3, 4, 7 };
int W = 11;
int z = W;
int n1 = r.Length;
stopwatch.Start();
int keik = knapSack(r, wt, n1 - 1, W);
stopwatch.Stop();

answer of this is 28, but I need to display all r numbers that was included in this. I know that for this array used numbers are 8 8 8 and 4, so I need somehow to get these numbers and display to the console.

knapsack-problem algorithm c#
1 Answers

You could try the approach of letting the function return the list of used items. You could either return the item values themselves, or the indices of the values, depending on your needs. I used the values in this example.

Here is an implementation:

static int knapSack(int[] r, int[] wt, int n, int W, out List<int> list)
{
    if (W < 0) {
        list = new List<int>();
        return Int32.MinValue;
    }
    if (n < 0 || W == 0) {
        list = new List<int>();
        return 0;
    }
    int include = r[n] + knapSack(r, wt, n, W - wt[n], out List<int> includedList);
    int exclude = knapSack(r, wt, n - 1, W, out List<int> excludedList);
    if (include > exclude) {
        includedList.Add(r[n]);
        list = includedList;
        return include;
    } else {
        list = excludedList;
        return exclude;
    }
}

Call like this:

int keik = knapSack(r, wt, n1 - 1, W, out List<int> list);
Console.WriteLine(string.Join(",", list));

Output:

4,8,8,8
user_15638330
Related