Source/AdvancedAlgorithms/Knapsack/GetKnapsack.cs
|
using System;
using System.Collections.Generic; using System.Text; using System.Management.Automation; using System.Reflection; namespace Knapsack { [Cmdlet("Get", "Knapsack")] public class GetKnapsack : PSCmdlet { #region Parameters [Parameter(Mandatory = true)] public int KnapsackSize { get; set; } [Parameter(Mandatory = true)] public PSObject[] Items { get; set; } [Parameter(Mandatory = true)] public string WeightPropertyName { get; set; } [Parameter(Mandatory = false)] public string ValuePropertyName { get; set; } #endregion #region Variables #endregion #region Cmdlet Functions protected override void ProcessRecord() { #region Parameter Checks // Check if knapsack size is 0 if (KnapsackSize <= 0) { WriteError(new ErrorRecord((new Exception("Knapsack size should be greater than 0.")), null, ErrorCategory.InvalidArgument, null)); return; } // Check if Items is null if ( !(Items != null)) { WriteError(new ErrorRecord((new Exception("Input items cannot be null.")), null, ErrorCategory.InvalidArgument, null)); return; } if (Items.Length == 0) { WriteError(new ErrorRecord((new Exception("Input item collection cannot be empty.")), null, ErrorCategory.InvalidArgument, null)); return; } // Check if WeightPropertyName exists foreach(PSObject o in Items) { try { GetPSObjectProperty(o, WeightPropertyName); } catch (Exception e) { WriteError(new ErrorRecord((new Exception("Could not find Weight property " + WeightPropertyName + " on all input objects.")), null, ErrorCategory.InvalidArgument, null)); return; } } // Check if the value property name is supplied if (!(ValuePropertyName != null)) ValuePropertyName = WeightPropertyName; else { foreach (PSObject o in Items) { try { GetPSObjectProperty(o, ValuePropertyName); } catch (Exception e) { WriteError(new ErrorRecord((new Exception("Could not find Value property " + ValuePropertyName + " on all input objects.")), null, ErrorCategory.InvalidArgument, null)); return; } } } #endregion #region Knapsack // Get the result List<PSObject> result = knapsack(KnapsackSize, Items, WeightPropertyName, ValuePropertyName, Items.Length); // Return the objects to select foreach (PSObject o in result) WriteObject(o); #endregion } #endregion #region Utility Functions /// <summary> /// Calculate the knapsack selection /// </summary> /// <param name="KnapsackSize"></param> /// <param name="Items"></param> /// <param name="WeightPropertyName"></param> /// <param name="ValuePropertyName"></param> /// <param name="n"></param> /// <returns></returns> protected static List<PSObject> knapsack(int KnapsackSize, PSObject[] Items, string WeightPropertyName, string ValuePropertyName, int n) { // Create seperate variables for the names of the properties in order to handle them as case-insensitive string weightPropertyName = string.Empty; string valuePropertyName = string.Empty; // Find the exact name of the properties to use foreach (System.Management.Automation.PSPropertyInfo pi in Items[0].Properties) { if (pi.Name.ToLower().Equals(WeightPropertyName.ToLower())) { weightPropertyName = pi.Name; } if (pi.Name.ToLower().Equals(ValuePropertyName.ToLower())) { valuePropertyName = pi.Name; } } // Create an array of weights to make calculations easier List<Int64> weightsList = new List<Int64>(); // Create an array of values to make calculations easier List<Int64> valuesList = new List<Int64>(); // Populate the lists foreach (PSObject o in Items) { // Get the values of the properties Int64 w1 = Convert.ToInt64(GetPSObjectPropertyValue(o, weightPropertyName)); Int64 v1 = Convert.ToInt64(GetPSObjectPropertyValue(o, valuePropertyName)); // Add the values to the lists weightsList.Add(w1); valuesList.Add(v1); } #region Knapsack Algorithm Int64 i, w; Int64[,] K = new Int64[n + 1, KnapsackSize + 1]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= KnapsackSize; w++) { if (i == 0 || w == 0) K[i, w] = 0; else if (weightsList[(int)(i - 1)] <= w) K[i, w] = Math.Max(valuesList[(int)(i - 1)] + K[i - 1, w - (Int64)weightsList[(int)(i - 1)]], K[i - 1, w]); else K[i, w] = K[i - 1, w]; } } // Save the optimum result Int64 res = K[n, KnapsackSize]; // Create a list to save the selected objects List<PSObject> selection = new List<PSObject>(); w = KnapsackSize; for (i = n; i > 0 && res > 0; i--) { // either the result comes from the top // (K[i-1][w]) or from (val[i-1] + K[i-1] // [w-wt[i-1]]) as in Knapsack table. If // it comes from the latter one/ it means // the item is included. if (res == K[i - 1, w]) continue; else { // This item is included. //Console.Write(weightsList[(int)(i - 1)] + " "); selection.Add(Items[(int)(i - 1)]); // Since this weight is included its // value is deducted res = res - valuesList[(int)(i - 1)]; w = w - weightsList[(int)(i - 1)]; } } #endregion // Return the list of selected objects return selection; } /// <summary> /// Get the information regarding a property of a Powershell object /// </summary> /// <param name="o"></param> /// <param name="PropertyName"></param> /// <returns></returns> protected static System.Management.Automation.PSPropertyInfo GetPSObjectProperty(PSObject o, string PropertyName) { foreach (System.Management.Automation.PSPropertyInfo pi in o.Properties) { if (pi.Name.ToLower().Equals(PropertyName.ToLower())) { return pi; } } return null; } /// <summary> /// Get the value of a specific property of a Powershell object /// </summary> /// <param name="o"></param> /// <param name="PropertyName"></param> /// <returns></returns> protected static object GetPSObjectPropertyValue(PSObject o, string PropertyName) { foreach (System.Management.Automation.PSPropertyInfo pi in o.Properties) { if (pi.Name.ToLower().Equals(PropertyName.ToLower())) { return pi.Value; } } return null; } #endregion } } |