//贪婪算法计算背包问题 public static double ksack(double[] values, double[] weights, int capacity) { double load = 0; int i = 0; double w = 0; while (load<capacity && i<values.Length) { if (weights[i] <= (capacity-load)) { w += values[i]; load += weights[i]; } else { double r = (capacity - load) / weights[i]; w += r * values[i]; load += weights[i]; } i++; } return w; }
//递归计算背包问题
public static int max(int a, int b)
{
return a > b ? a : b;
}
public static int knapsack(int cappcity, int[] size, int[] value, int n)
{
if (n == 0 || cappcity == 0)
{
return 0;
}
if (size[n - 1] > cappcity)
{
return knapsack(cappcity, size, value, n - 1);
}
else
{
return max(value[n - 1] + knapsack(cappcity - size[n - 1], size, value, n - 1), knapsack(cappcity, size, value, n - 1));
}
}
//动态规划背包问题
public static long dKnapsack(int cappcity, int[] size, int[] value, int n)
{
int[,] K = new int[n, cappcity + 1];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < cappcity; j++)
{
K[i, j] = 0;
}
}
for (int i = 0; i < n; i++)
{
for (int w = 0; w < cappcity; w++)
{
if (i == 0 || w == 0)
{
K[i,w] = 0;
}
else if (size[i - 1] <= w)
{
K[i,w] = max(value[i - 1] + K[i - 1,w-size[i-1]], K[i - 1,w]);
}
else
{
K[i,w] = K[i - 1,w];
}
}
}
return K[n,cappcity];
}