Knapsack Problem - recursive, C#

Knapsack Problem - recursive

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        // Knapsack Problem - recursive
        public static void Main(string[] args)
        {
            int [] values = new int[]{60, 100, 120}; 
            int [] weights = new int[]{10, 20, 30}; 
            int capacity = 50; 
            int n = values.Length; 
            Console.WriteLine(knapSack(capacity, weights, values, n)); 
        }
    
        //It returns maximum of two integers 
        static int max(int a, int b) { 
            return (a > b)? a : b;  
        } 
      
        // Returns the maximum value that can be put in a knapsack of capacity 
        static int knapSack(int capacity, int [] weights,  int [] values, int n) {

// Base Case - nothing can be included in knapSack as capacity is 0 or no values exists.
            if (n == 0 || capacity == 0) 
                return 0;

// If weight of the nth item is  more than Knapsack capacity , then this item cannot be  included in the optimal solution 
            if (weights[n-1] > capacity) 
                return knapSack(capacity, weights, values, n-1);

// Return the maximum of two cases:  
            // 1. inclusing nth item   
            // 2. without including nth item. 
            else return max( values[n-1] + knapSack(capacity - weights[n-1], weights, values, n-1), 
                       knapSack(capacity, weights, values, n-1)); 
        } 
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development