algorithm - 背包算法变量

Question

我遇到的问题如下：
假设我有一个给定重量的存钱罐，我正在用一组给定的硬币存钱。最后，我知道了存钱罐的总重量以及我使用的硬币的重量和价值。

我想找出我可以保证存入存钱罐的最低金额，即最坏的情况。例如，如果：

• 总重量 = 100
• 使用的硬币重量 = {1, 50}
• 硬币的价值 = {1, 30}

那么我可以保证的银行最低值是60。

问题是背包变体，但我无法找到正确的重复出现。

提前致谢！

Answer 1

我处理这个问题的方法是评估集合中的每个硬币以确定它的“价值密度”（因为需要一个更好的术语）——价值除以重量。在您的示例中，第一枚硬币的价值密度为 1，然后第二枚硬币的价值密度为 30/50 = 0.6。

然后从总重量为零开始，在不超过给定重量的情况下使用最低的“价值密度”硬币。然后应用下一个最低的“价值密度”硬币，依此类推，直到达到给定的重量。

这大致是一种贪心算法。

Answer 2

显然你知道这个问题，但你想得到一种计算解决方案的方法^^。

对于精确的方法，您可以查看分支定界算法。这是一种相对简单的 OR 方法，可以找到背包问题的确切解决方案，你应该找到很多关于它的课程。

Vicky 提交了一个很好的解决方案来计算分支定界算法的下限。

Answer 3

通常背包问题AFAIK只有指数解决方案。也就是说，假设您拥有特定数量的每种硬币。在最一般的情况下，您必须尝试所有可能的组合（当然不超过总重量）。

递归算法如下所示：

const int N = /* type count*/;

const int g_Weight[N] = { ... };
const int g_Value[N] = { ... };

int CalcMinValueFrom(int weight, int i)
{
    int valBest = 0, valMy = 0;

    if (weight <= 0)
        return 0; // weight already reached

    if (i >= N)
        return -1; // out of coins

    while (true)
    {
        int valNext = CalcMinValueFrom(weight, i+1);
        if (valNext >= 0)
        {
            valNext += valMy;
            if (!valBest || (valBest > valNext))
                valBest = valNext;
        }

        valMy += g_Value[i];
        weight -= g_Weight[i];

        if (valBest && (valBest <= valMy))
            return valBest;
    }
}

// Returns the minimum value for the given weight    
int CalcMinValue(int weight)
{
    return CalcMinValueFrom(weight, 0);
}

然而，在特定情况下，存在更好的解决方案。如果重量远大于任何硬币的重量，那么您可以很容易地粗略估计结果。将每枚硬币的“效率”定义为其价值和重量之间的比率。为了使价值最小化，您应该只选择“效率”最低的硬币。该解决方案精确到“边缘效应”，例如四舍五入等（意味着 - 你只能取整数个硬币）。