0

每个项目都有三个属性

  • 物品大小 S i
  • 项目 V i的价值
  • 将物品放入背包所需的最小值 M i (<= 10 7 )

最多将有 100 个项目。

我们得到背包的大小 K (K <= 1000) 和初始值 V（在背包中不占空间）。当且仅当 M i小于或等于 V
时，才能将物品“i”放入背包中。在背包中添加物品后，V 增加了 V i。我们必须最大化放入给定尺寸背包的物品数量（而不是价值）。

我发现这个问题很相似。但是答案中描述的算法是立方时间，对于这个问题来说不够快。我们如何以更好的方式解决这个问题？

4

1 回答 1

1

我可以在这里给出一个 O(n^3) 算法。不知道这个问题是否可以进一步优化到O(n^2)。

首先，这个问题是最大化if items的数量，这与其他背包问题有点不同。同时，它也有一个限制，即只有当背包的总价值大于其自身价值时，才能选择单个物品。所以一个明显的推论是，在选择相同数量的物品和固定总大小的情况下，总价值应该尽可能大（以便可以将更多物品添加到背包中）。

注意物品的数量n(<=100)和背包的大小K(<=1000)不是很大，设f[i][j]表示选择i个总大小为j的物品时的最大值。最初，所有 f[i][j] 都设置为 0，除了 f[0][0]=V。

然后根据需要添加的最小值对项目进行排序。这是一个贪心的想法，因为在排序之后，我们只能遍历每个项目一次。

DP 方法如下所示：

for (int k=0;k<n;k++) //iterate items
    for (int i=n;i>=0;i--)
        for (int j=K;j>=0;j--) if (item.M[k]<=f[i][j])
            f[i+1][j+item.S[k]]=max(f[i+1][j+item.S[k]],f[i][j]+item.V[k]);

最终答案（最大项目数）是：

for (int i=n;i>=0;i--)
    for (int j=0;j<=K;j++)
        if (f[i][j]) return i;
于 2013-04-01T03:28:55.213 回答