dynamic - 背包（多标准）

Question

如果我有一个背包，其中重量 w 有两个值 v1 和 v2，容量为 m。如何找到重量不超过容量 m 的 v1 和 v2 的总值？

Answer 1

好的，所以您的问题定义如下。首先是一些（带有样本值的变量定义）：

int N = 4; // number of items to choose from
int m = 6; // maximum weight in knapsack

// weight for an item[i] to be summed up, upper limited = m
int weight[N] = {5,2,4,3}; 

// two values for each items:
int values[2][N] = {
  {1,3,5,2},
  {6,3,2,4}
};

背包应装满物品，背包中所有物品的重量总和不得超过重量“m”。每个项目都有 2 个值。我们可以把这个问题看作：

我想和女朋友一起坐飞机去度假。我们有一个手提箱（=背包）和 N 件物品可供选择。每件物品都有一个重量，重量之和不能太高（例如重量限制航空线是25公斤，行李箱是1公斤，所以我们有m=24公斤作为物品的限制）。对于每个项目，我们有 2 个值。values[1][N] 是我的值（用于在我们的旅行中将项目 n 放入背包中）。values[2][N] 是我女朋友的值，她有不同的喜好。我们还假设，每件物品只能放入背包一次，背包的总价值是它们对我的价值之和加上它们对她的价值之和。

只需将值列表相加，这个问题就可以很容易地转换为标准背包问题。所以一个项目获得一个整体价值（例如，我和她一起），我们只有一个项目的一个价值：

int value[N] = {(1+6),(3+3),(5+2),(2+4)};

要不就：

int value[N] = {7, 6, 7, 5};

现在每个项目只有 -one- 值。这是正常的背包问题。

Wikipedia 上描述了如何以最佳方式解决常见的背包问题。查看http://en.wikipedia.org/wiki/Knapsack_problem -- 如果英语不是您的母语，也请查看您的语言版本（从那里的菜单中选择语言）。

如果您需要进一步的帮助，请询问。