分数背包问题：带有示例的贪心算法
陈莎拉
什么是贪心策略？
贪心算法类似于动态规划算法，通常用于解决最优问题（根据特定准则找到问题的最佳解决方案）。
贪婪算法实现最优局部选择，希望这些选择能够为待解决的问题带来最优全局解决方案。 贪心算法通常不太难设置，速度很快（时间复杂度通常是线性函数或非常二阶函数）。 此外，这些程序不难调试并且使用更少的内存。 但结果并不总是最优解。
贪心策略通常用于通过构建选项 A 来解决组合优化问题。选项 A 是通过选择 A 的每个组件 Ai 直到完成（足够的 n 个组件）来构建的。 对于每个 Ai，您选择最佳的 Ai。 这样，有可能在最后一步你除了接受最后剩下的值之外别无选择。
贪婪决策有两个关键组成部分：
- 贪心选择的方式。 您可以选择当前最好的解决方案，然后解决因做出最后选择而产生的子问题。 贪心算法的选择可能取决于先前的选择。 但它不能依赖于任何未来的选择或依赖于子问题的解决方案。 该算法以在循环中进行选择的方式发展，同时将给定问题缩小为更小的子问题。
- 最优子结构。 如果问题的最优解包含其子问题的最优解，则可以执行问题的最优子结构。
贪心算法有五个组成部分：
- 一组候选人，从中创建解决方案。
- 选择函数，选择最佳候选者添加到解决方案中。
- 可行函数用于决定候选者是否可用于构建解决方案。
- 一个目标函数，确定解决方案或不完整解决方案的价值。
- 评估函数，指示您何时找到完整的解决方案。
贪心者的想法
有了第一个思路，你就有了Greedy One的以下步骤：
- 按值的非递增顺序排序。
- 依次考虑订购的包裹，如果背包的剩余容量足以容纳它，则将考虑的包裹放入背包（这意味着已经放入背包的包裹的总重量和考虑的包裹的重量不超过背包的容量）。
然而，这种贪心算法并不总能给出最优解。 这里有一个反例：
- 问题的参数是：n = 3； 米 = 19。
- 包：{i = 1; W[i] = 14; V[i] = 20}; {我 = 2; W[i] = 6; V[i] = 16}; {我= 3; W[i] = 10; V[我] = 8} -> 物超所值，但重量也很大。
- 该算法将选择总值为 1 的包 20，同时选择问题的最优解（包 2、包 3），总值为 24。
贪心二的思想
有了第二个思路，你就有了Greedy Two的以下步骤：
- 按权重非降序排列。
- 依次考虑订购的包裹，如果背包的剩余容量足以容纳它，则将考虑的包裹放入背包（这意味着已经放入背包的包裹的总重量和考虑的包裹的重量不超过背包的容量）。
然而，这种贪心算法并不总能给出最优解。 这里有一个反例：
- 问题的参数是：n = 3； 米 = 11。
- 包：{i = 1; W[i] = 5; V[i] = 10}; {我 = 2; W[i] = 6; V[i] = 16}; {我= 3; W[i] = 10; V[我] = 28} -> 重量轻但价值也很轻。
- 算法会选择总值为1的(package 2, package 26)，而问题的最优解是(package 3)总值为28。
贪心三的思想
有了第三个想法，你就有了贪婪三的以下步骤。 事实上，这是使用最广泛的算法。
- 按单位成本值不增加的顺序对包裹进行排序
. 你有：
- 依次考虑订购的包裹，如果背包的剩余容量足以容纳它，则将考虑的包裹放入背包（这意味着已经放入背包的包裹的总重量和考虑的包裹的重量不超过背包的容量）。
主意: 该问题的贪心思想是计算 
每个的比率 
. 然后按降序对这些比率进行排序。 你会选择最高的 包裹和背包的容量可以包含该包裹（保持> wi）。 背包中每放入一个包裹，也会减少背包的容量。
套餐选择方式：
- 考虑单位成本的数组。 您根据递减的单位成本选择套餐。
- 假设您找到了部分解决方案：(x1，…， Xi).
- 获得背包的价值：
- 对应已放入背包的包裹重量：
- 因此，背包的剩余重量限制为：
算法步骤
你看这是一个寻找最大值的问题。 包列表按单位成本降序排列以考虑分支。
- 第一步：节点根代表背包的初始状态，此时你还没有选择任何包裹。
- 总值 = 0。
- 根节点的上限 UpperBound = M * 最大单位成本。
- 第一步：节点根会有子节点对应选择单位成本最大的包的能力。 对于每个节点，您重新计算参数：
- TotalValue = TotalValue（旧）+ 所选包裹的数量 * 每个包裹的价值。
- M = M（旧）- 所选包裹的数量 * 每个包裹的重量。
- UpperBound = TotalValue + M (new) * 接下来要考虑的打包的单位成本。
- 第一步：在子节点中，您将优先为具有较大上限的节点进行分支。 该节点的子节点对应于选择下一个单位成本大的包裹的能力。 对于每个节点，必须根据步骤2中提到的公式重新计算参数TotalValue、M、UpperBound。
- 第一步：重复步骤 3，注意：对于上限低于或等于找到的选项的临时最大成本的值的节点，您不需要再为该节点分支。
- 第一步：如果所有节点都被分支或切断，则最昂贵的选项是要寻找的选项。
该算法的伪代码：
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
算法的复杂度：
- 如果使用简单的排序算法（选择、冒泡……），那么整个问题的复杂度为 O(n2)。
- 如果使用快速排序或归并排序，那么整个问题的复杂度为 O(nlogn)。
Java 贪婪三人组的代码
- 首先，定义类 KnapsackPackage。 这个类有属性是：每个包裹的重量、价值和相应的成本。 此类的属性成本用于主算法中的排序任务。 每个成本的价值是
每个包的比例。
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- 然后创建一个函数来执行贪婪三算法。
public void knapsackGreProc(int W[], int V[], int M, int n) {
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int i = 0; i < n; i ++) {
packs[i] = new KnapsackPackage(W[i], V[i]);
}
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
代码说明：
- 初始化每个背包包的重量和价值。
- 按成本降序排列背包包裹。
- 如果选择包 i。
- 如果选择包数 i 就足够了。
- 浏览所有包时停止。
在本教程中，您有两个示例。 这是运行上述程序的 java 代码，有两个示例：
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
你有输出：
- 第一个例子：
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- 第二个例子：
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
分析第一个例子：
- 问题的参数是：n = 4； 米 = 37。
- 包：{i = 1; W[i] = 15; V[i] = 30; 成本 = 2.0}; {我 = 2; W[i] = 10; V[i] = 25; 成本 = 2.5}; {我= 3; W[i] = 2; V[i] = 4; 成本 = 1.0}; {我= 4; W[i] = 4; V[i] = 6; 成本 = 1.5}。
- 您按照单位成本值不增加的顺序对包裹进行排序。 你有：{i = 2} -> {我 = 1} -> {我 = 4} -> {我 = 3}。
第一个例子应用算法的步骤：
- 定义x1,x2,x3,x4为每个选中包的编号，对应包{i = 2} -> {我 = 1} -> {我 = 4} -> {我 = 3}。
- 节点根 N 代表你没有选择任何包的状态。 然后：
- 总值 = 0。
- M = 37（建议）。
- UpperBound = 37 * 2.5 = 92.5，其中37为M，2.5为包裹{i = 2}的单位成本。
- 对于包裹 {i = 2}，您有 4 种可能性：选择 3 包裹 {i = 2} (x1 = 3)； 选择 2 个包 {i = 2} (x1 = 2)； 选择 1 个包 {i = 2} (x1 = 1) 而不是选择包 {i = 2} (x1 = 0)。 根据这 4 种可能性，您将根节点 N 分支为 4 个子节点 N[1]、N[2]、N[3] 和 N[4]。
- 对于子节点 N1，您有：
- TotalValue = 0 + 3 * 25 = 75，其中 3 是所选包 {i = 2} 的数量，25 是每个包 {i = 2} 的价值。
- M = 37 – 3 * 10 = 7，其中37是背包的初始数量，3是包裹的数量{i = 2}，10是每个包裹的重量{i = 2}。
- UpperBound = 75 + 7 * 2 = 89，其中 75 是 TotalValue，7 是背包的剩余重量，2 是包裹的单位成本 {i = 1}。
- 同理，可以计算节点N[2]、N[3]、N[4]的参数，其中UpperBound分别为84、79、74。
- 在节点N[1]、N[2]、N[3]和N[4]中，节点N[1]的UpperBound最大，所以先分支节点N[1]，希望有一个这个方向的好计划。
- 从节点N[1]开始，你只有一个子节点N[1-1]对应x2 = 0（由于背包剩余重量为7，而每个包裹{i = 1}的重量为15） . 确定 N[1-1] 按钮的参数后，您的 N[1-1] 的 UpperBound 为 85.5。
- 您继续分支节点 N[1-1]。 节点 N[1-1] 有 2 个子节点 N[1-1-1] 和 N[1-1-2] 对应于 x3 = 1 和 x3 = 0。确定这两个节点的参数后，您会看到N[1-1-1]的UpperBoundary为84，N[1-1-2]的UpperBoundary为82，继续分支节点N[1-1-1]。
- 节点N[1-1-1]有两个孩子N[1-1-1-1]和N[1-1-1-2]，对应x4 = 1和x4 = 0。这是两个叶子节点（代表选项）因为每个节点都选择了包的数量。 其中节点N[1-1-1-1]代表选项x1 = 3, x2 = 0, x3 = 1 and x4 = 1 for 83, 而节点N[1-1-1-2]代表选项x1 = 3, x2 = 0, x3 = 1 and x4 = 01 at 81. 所以这里暂时的最大值是83.
- 回到节点 N[1-1-2]，您会看到 N[1-1-2] 的 UpperBound 是 82 < 83，因此您修剪节点 N[1-1-2]。
- 回到节点N2，看到N2的UpperBound为84 > 83，继续分支节点N2。 节点 N2 有两个子节点 N[2-1] 和 N[2-2] 对应于 x2 = 1 和 x2 = 0。计算 N[2-1] 和 N[2-2] 的参数后，您会看到N[2-1] 的 UpperBound 是 83，N[2-2] 的 UpperBound 是 75.25。 这些值都不大于 83，因此两个节点都被修剪。
- 最后，节点 N3 和 N4 也被修剪。
- 所以树上的所有节点都被分支或修剪，因此最好的临时解决方案是要寻找的解决方案。 因此，您需要选择3件包裹{i = 2}、1件包裹{i = 4}和3件包裹{i = 83}，总价值为36，总重量为XNUMX。
通过对第二个示例的相同分析，您得到的结果是：选择包 4（3 次）和包 5（3 次）。
Python贪婪三人行的 3 个代码
- 首先，定义类 KnapsackPackage。
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
- 然后创建一个函数来执行贪婪三算法。
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
代码说明：
- 初始化每个背包包的重量和价值。
- 按成本降序排列背包包裹。
- 如果选择包 i。
- 如果选择包数 i 就足够了。
- 浏览所有包时停止。
这是 Python3 使用第一个例子来运行上面的程序的代码：
if __name__ == "__main__":
W = [15, 10, 2, 4]
V = [30, 25, 2, 6]
M = 37
n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
你有输出：
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
贪婪三的 C# 代码
- 首先，定义类 KnapsackPackage。
using System;
namespace KnapsackProblem
{
public class KnapsackPackage
{
private double weight;
private double value;
private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- 然后创建一个函数来执行贪婪三算法。
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
代码说明：
- 初始化每个背包包的重量和价值。
- 按成本降序排列背包包裹。
- 如果选择包 i。
- 如果选择包数 i 就足够了。
- 浏览所有包时停止。
这是使用第一个示例运行上述程序的 C# 代码：
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
你有输出：
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
贪心三的反例
贪心三的算法求解很快，在某些情况下也可以是最优的。 但在某些特殊情况下，并不能给出最优解。 这里有一个反例：
- 问题的参数是：n = 3； 米 = 10。
- 包：{i = 1; W[i] = 7; V[i] = 9; 成本 = 9/7}； {我 = 2; W[i] = 6; V[i] = 6; 成本 = 1}; {我= 3; W[i] = 4; V[i] = 4; 成本 = 1}。
- 算法会选择总值为1的（包9），而问题的最优解为（包2，包3）总值为10。
下面是使用反例运行上述程序的 java 代码：
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
结果如下：
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
这就是分数背包问题的全部内容。
