0/1背包 - 对维基的伪code一些澄清 [英] 0/1 Knapsack - A few clarification on Wiki's pseudocode

问题描述

下面是对en.wikipedia对背包问题的文章code：

  //输入：
//值（存储在数组v）的
//重量（存储在数组w）
//不同项目数（n）的
//背包容量（W）
用W 0至W待办事项
  米[0，瓦特]：= 0
结束了
对于i从1到n做
  对于j从0到w请勿
    如果J＆GT; = W [I]，然后
      米[I，J]：=最大值（米[I-1，j]的，米[I-1，J-瓦特[I] + V [I]）
    其他
      米[I，J]：=米[I-1，j]的
    如果结束
  结束了
结束了
 

我有两点我疲倦的大脑不能工作了。他们是未成年人，我敢肯定，但我真的可以使用帮助。

•什么是M []数组的大小？ M [N，W]？如果是，是伪code忽略最后一行及最后一列，因为它填补用零整个第一行（for（）循环具有m [0，瓦特]：= 0），然后从循环1到n，和0到W例如，对于3种不同的项目（N == 3）和一个容量为4（W == 3），是米[3,4]或米[4,5] <？ / P>

•是否有一个动态的背包算法中的更好的例子，什么地方？

解决方案

的阵列的大小为（n + 1）次; （W + 1）时，由于值在范围[0，0]到[n及W]以下。

网格的帧间pretation如下：位置[K，W]重新presents的值，可以从使用​​前k项（假设项编号1得到最大的量， 2，...，n）和携带不超过瓦特总重量更

的原因，第一行被设置完全为0是因为任何条目的形式的[0，瓦特]对应于可以使用第一项0和携带至多瓦特重量得到的最大值。这是始终为零，因为你永远无法通过不接任何项目的任何值。这对应于递归基本案例

行之后的第一个填充使用下面的方法：如果你想尝试采摘的第k个项目，你首先需要确保你必须按住它（意味着能力的W具有至少为W¯¯ [K]）。如果你不能拿着它，你最好的选择就是让最前k - 1项符合目前的体重限制（所以你最好是去采取相应m的值[K - 1，W]如果你能坚持的项目，你的选择是要么不把它（和以前一样，使大多数的其他项目，产生M [ - 1，W]），或者把它和最大限度的剩余，搭载其余项目的能力这给你值V [K] + M [K - 1，W - W [K]]。

希望这有助于！

Here's the code on en.wikipedia's article on the Knapsack problem:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

I've got two points which my tired brain cannot work out. They're minor, I'm sure, but I could really use the help.

•What's the size of the m[] array? m[n,W]? If it is, is the pseudocode ignoring the last line and last column, because it fills the entire first line with zeroes (the for() loop with m[0,w] := 0), and then loops from 1 to n, and 0 to W. For example, for 3 different items (n==3) and a capacity of 4 (W==3), is m[3,4] or m[4,5]?

•Are there better examples of a dynamic knapsack algo, somewhere?

解决方案

The size of the array is (n + 1) × (W + 1), since the values range up from [0, 0] through [n, W] inclusive.

The interpretation of the grid is the following: position [k, w] represents the maximum amount of value that you can get from using the first k items (assuming the items are numbered 1, 2, ..., n) and carrying no more than w total weight.

The reason that the first row is set entirely to 0 is because any entry of the form [0, w] corresponds to the maximum value you can get using the first 0 items and carrying at most w weight. This is always zero, since you can never get any value by not picking any items. This corresponds to the base case of the recursion.

Rows after the first are filled in using the following idea: if you want to try picking the kth item, you would first need to make sure that you have the ability to hold it (meaning that w has to be at least w[k]). If you can't hold it, your best option is to make the most of the first k - 1 items subject to your current weight restriction (so you'd be best off taking the value corresponding to m[k - 1, w]. If you can hold the item, your options are either to not take it (and, as before, to make the most of the other items, yielding m[k - 1, w]), or to take it and maximize the remaining carrying capacity with the remaining items. This gives you value v[k] + m[k - 1, w - w[k]].

Hope this helps!

这篇关于0/1背包 - 对维基的伪code一些澄清的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！