Skip to content

Instantly share code, notes, and snippets.

@Big-al
Created September 26, 2020 23:46
Show Gist options
  • Save Big-al/14d68627601c8afd2d7d25b9a780da7a to your computer and use it in GitHub Desktop.
Save Big-al/14d68627601c8afd2d7d25b9a780da7a to your computer and use it in GitHub Desktop.
Unbounded minimum and maximum knapsack solver in c#
namespace UnboundedKnapsackSolvers
{
public class DriverProgram
{
// Driver program
public static void Main()
{
// Premise: We must use the entire Total Quantity.
int TQty = 36; // total quantity of the item
decimal[] val = { 6.95m, 59.95m, 19.95m }; // price for each set
int[] Q = { 1, 9, 3 }; // quantity that releases each set price
decimal min = MinUnboundedKnapsack.GetMinValue(TQty, val, Q);
decimal max = MaxUnboundedKnapsack.GetMaxValue(TQty, val, Q);
Console.WriteLine("MIN: " + min);
Console.WriteLine("MAX: " + max);
}
// Method to find MINIMUM achievable value with a TotalQuantity of TQty and
// multiple instances of the same Price / Quantity combo allowed.
public class MinUnboundedKnapsack
{
// Returns the Minimum value with a total quantity of TQty
public static decimal GetMinValue(int TQty, decimal[] val, int[] Q)
{
int n = val.Length;
// dp[i] is going to store minimum value with a total quantity of i.
decimal[] dp = new decimal[TQty + 1];
for (int i = 0; i <= TQty; i++)
{
for (int j = 0; j < n; j++)
{
if (Q[j] <= i)
{
decimal left = dp[i];
decimal right = dp[i - Q[j]] + val[j];
dp[i] = left == 0 ? right : Math.Min(left, right);
}
}
}
Console.WriteLine("------------ MIN ------------");
for (int i = 0; i <= TQty; i++)
{
Console.WriteLine("Quantity: " + i + " " + " has Min val: " + dp[i]);
}
return dp[TQty];
}
}
// Method to find MAXIMUM achievable value with a TotalQuantity of TQty and
// multiple instances of the same Price / Quantity combo allowed.
public class MaxUnboundedKnapsack
{
// Returns the maximum value with a total quantity of TQty
public static decimal GetMaxValue(int TQty, decimal[] val, int[] Q)
{
int n = val.Length;
// dp[i] is going to store maximum value with a total quantity of i.
decimal[] dp = new decimal[TQty + 1];
// Fill dp[] using the recursive formula:
for (int i = 0; i <= TQty; i++)
{
for (int j = 0; j < n; j++)
{
if (Q[j] <= i)
{
decimal left = dp[i];
decimal right = dp[i - Q[j]] + val[j];
dp[i] = Math.Max(left, right);
}
}
}
Console.WriteLine("------------ MAX ------------");
for (int i = 0; i <= TQty; i++)
{
Console.WriteLine("Quantity: " + i + " " + " has Max val: " + dp[i]);
}
return dp[TQty];
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment