Created
September 26, 2020 23:46
-
-
Save Big-al/14d68627601c8afd2d7d25b9a780da7a to your computer and use it in GitHub Desktop.
Unbounded minimum and maximum knapsack solver in c#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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