0/1 Knapsack problem using Iterative Approach, C#

0/1 Knapsack problem using Iterative Approach

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

namespace Rextester
{
    public class Program
    {
        static int Knapsack (Item[] items, int capacity)
        {
            //Tabulization
            var t = new int[items.Length+1, capacity+1];
            
            //Iterative approach
            for (int itemIndex=0; itemIndex <= items.Length; itemIndex++)
            {
                var currentItem = itemIndex == 0 ? null : items[itemIndex - 1];
                for (int currentCapacity = 0; currentCapacity <= capacity; currentCapacity++)
                {
                    //Base case
                    if (currentItem == null || currentCapacity == 0)
                        t[itemIndex, currentCapacity] = 0;
                    
                    //If need to be put current item in Knapsack
                    else if (currentItem.weight <= currentCapacity)
                    {
                        t[itemIndex, currentCapacity] = Math.Max (currentItem.value + t[itemIndex-1, currentCapacity-currentItem.weight], 
                                                                  t[itemIndex-1, currentCapacity]);
                    }
                    
                    //If not need to put current item in Knapsack
                    else
                    {
                        t[itemIndex, currentCapacity] = t[itemIndex-1, currentCapacity];
                    }
                    
                    //Printing table for Visualization purpose
                    Console.WriteLine($"currentItem={currentItem?.value} \t currentCapacity= {currentCapacity}");
                    printMatrix (t, items.Length, capacity);
                }
            }
            
            return t[items.Length, capacity];
        }
        
        private static void printMatrix (int[,] mat, int n, int capacity)
        {
            Console.WriteLine("----------------------------------------------------------------------------------");
            for (int itemIndex=0; itemIndex <= n; itemIndex++)
            {
                for (int currentCapacity = 0; currentCapacity <= capacity; currentCapacity++)
                {
                    Console.Write(mat[itemIndex, currentCapacity] + "\t");
                }
                
                Console.WriteLine("");
            }
            Console.WriteLine("----------------------------------------------------------------------------------\n");
        }
        
        public static void Main(string[] args)
        {
            var items = new[]
            {
                new Item {value = 10, weight = 1},
                new Item {value = 20, weight = 1},
                new Item {value = 30, weight = 1},
                new Item {value = 50, weight = 1},
                new Item {value = 70, weight = 1},
            };

Console.WriteLine(Knapsack(items, 2));
        }
    }
    
    public class Item 
    {
        public int value;
        public int weight;
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development