LargestSmallerSum.cs

using System;
using System.Collections.Generic;
                    
public class Program
{
    public static void Main()
    {
        int[] values = {110, 100, 200 };
        int[] weights = {10, 20, 30};
        int maxWeight = 30;
        
        Console.WriteLine(Knapsack(maxWeight, weights, values));
    }
    
    public static int Knapsack(int maxWeight, int[] wts, int[] vals)
    {
        var totalWeightsValues = new HashSet<Tuple<int, int>>(); // weight/value
        totalWeightsValues.Add(new Tuple<int, int>(0,0));
        int maxValue = 0;
        
        for (var i = 0; i < wts.Length; i++)
        {
            var totalWeightsValuesTmp = new HashSet<Tuple<int, int>>();
            
            foreach (var wv in totalWeightsValues)
            {
                var weight = wv.Item1 + wts[i];
                
                if (weight > maxWeight)
                {
                    continue;    
                }
                
                var value = wv.Item2 + vals[i];
                
                totalWeightsValuesTmp.Add(new Tuple<int, int>(weight, value));
                maxValue = Math.Max(maxValue, value);
            }
            
            foreach (var tmp in totalWeightsValuesTmp)
            {
                totalWeightsValues.Add(tmp);
            }
        }
        
        return maxValue;
    }
    
    public static int LargestSmallerSum(int[] arr, int lookup)
    {
        var sums = new HashSet<int>();
        sums.Add(0);
        int optimal = int.MinValue;
        
        // N
        
        for (var i = 0; i < arr.Length; i++)
        {
            var tempSums = new HashSet<int>();
            
            foreach (var sum in sums)
            {
                var tmpSum = sum + arr[i];
                
                if (tmpSum == lookup)
                {
                    return lookup;
                }
                
                if (tmpSum < lookup)
                {
                    optimal = Math.Max(optimal, tmpSum);
                    tempSums.Add(tmpSum);    
                }
            }
            
            foreach (var s in tempSums)
            {
                sums.Add(s);    
            }
        }
        
        return optimal;
    }
}