public static int CalculateBagProblem(int BagVolumn, List<int> items, out List<int> chosenItems)
{
chosenItems = new List<int>();
if (items.Count == 0)
{
return 0;
}
else if (items.Count == 1)
{
if (items[0] <= BagVolumn)
{
chosenItems.Add(items[0]);
return items[0];
}
else
{
return 0;
}
}
else
{
// without the first item
List<int> remainItems = items.GetRange(1, items.Count - 1);
List<int> chosenItemsInRemainItems = new List<int>();
int withoutFirstItemResult = CalculateBagProblem(BagVolumn, remainItems, out chosenItemsInRemainItems);
// with all the items
int withFirstItemResult = 0;
List<int> chosenItemsInItems = new List<int>();
if (BagVolumn >= items[0])
{
withFirstItemResult = CalculateBagProblem(BagVolumn - items[0], remainItems, out chosenItemsInItems) + items[0];
chosenItemsInItems.Add(items[0]);
}
// select max from the two results
if (withoutFirstItemResult >= withFirstItemResult)
{
chosenItems = chosenItemsInRemainItems;
return withoutFirstItemResult;
}
else
{
chosenItems = chosenItemsInItems;
return withFirstItemResult;
}
}
}
No comments:
Post a Comment