数据结构（C#)- 贪心算法解决背包有关问题
日期：2014-05-17 浏览次数：21003 次
数据结构（C#)-- 贪心算法解决背包问题
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data ;
using System.Collections ;
namespace Kapbag
{
public class Knapsack
{
private float quantity;
SortedList items = new SortedList();
string itemList;
public Knapsack(float max)
{
quantity = max;
}
public void FillSack(ArrayList objects)
{
int pos = objects.Count - 1;
int totalUnits = 0;
float totalVal = 0.0F;
int tempTot = 0;
while (totalUnits < quantity)
{
tempTot += ((Carpet)objects[pos]).GetUnit();
if (tempTot <= quantity)
{
totalUnits += ((Carpet)objects[pos]).GetUnit();
totalVal += ((Carpet)objects[pos]).GetVal();
items.Add(((Carpet)objects[pos]).GetItem(), ((Carpet)objects[pos]).GetUnit());
}
else
{
float tempUnit = quantity - totalUnits;
float tempVal = ((Carpet)objects[pos]).ItemVal() * tempUnit;
totalVal += tempVal;
totalUnits += (int)tempUnit;
items.Add(((Carpet)objects[pos]).GetItem(), tempUnit);
}
pos--;
}
}
public string GetItems()
{
foreach (Object k in items.GetKeyList())
itemList += k.ToString() + ": " + items[k].
ToString() + " ";
return itemList;
}
static void Main()
{
Carpet c1 = new Carpet("Frieze", 1.75F, 12);
Carpet c2 = new Carpet("Saxony", 1.82F, 9);
Carpet c3 = new Carpet("Shag", 1.5F, 13);
Carpet c4 = new Carpet("Loop", 1.77F, 10);
ArrayList rugs = new ArrayList();
rugs.Add(c1);
rugs.Add(c2);<
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data ;
using System.Collections ;
namespace Kapbag
{
public class Knapsack
{
private float quantity;
SortedList items = new SortedList();
string itemList;
public Knapsack(float max)
{
quantity = max;
}
public void FillSack(ArrayList objects)
{
int pos = objects.Count - 1;
int totalUnits = 0;
float totalVal = 0.0F;
int tempTot = 0;
while (totalUnits < quantity)
{
tempTot += ((Carpet)objects[pos]).GetUnit();
if (tempTot <= quantity)
{
totalUnits += ((Carpet)objects[pos]).GetUnit();
totalVal += ((Carpet)objects[pos]).GetVal();
items.Add(((Carpet)objects[pos]).GetItem(), ((Carpet)objects[pos]).GetUnit());
}
else
{
float tempUnit = quantity - totalUnits;
float tempVal = ((Carpet)objects[pos]).ItemVal() * tempUnit;
totalVal += tempVal;
totalUnits += (int)tempUnit;
items.Add(((Carpet)objects[pos]).GetItem(), tempUnit);
}
pos--;
}
}
public string GetItems()
{
foreach (Object k in items.GetKeyList())
itemList += k.ToString() + ": " + items[k].
ToString() + " ";
return itemList;
}
static void Main()
{
Carpet c1 = new Carpet("Frieze", 1.75F, 12);
Carpet c2 = new Carpet("Saxony", 1.82F, 9);
Carpet c3 = new Carpet("Shag", 1.5F, 13);
Carpet c4 = new Carpet("Loop", 1.77F, 10);
ArrayList rugs = new ArrayList();
rugs.Add(c1);
rugs.Add(c2);<
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
