每月存档：7月 2009

背包问题：

现有 n 件物品，一个最大容量为 maxWeight 的背包。第 i 件物品重量为 weights[i] ，价值为 values[i] 。如果是0/1背包，对于一件物品，你必须选择取或不取，且每件物品只能被取一次（这就是“0/1”的含义）；如果是完全背包，你可以选择任意多件。

求放置哪几件物品进背包，使得背包中物品价值最大。

思路：推荐

• 0/1背包
• 完全背包

说的清清楚楚地。

代码最实际了：
0/1背包

public static int unpack(int[] values, int[] weights, int maxWeight) {
  int[] ans = new int[maxWeight + 1];
  for (int i = 0; i < values.length; i++) {
    for (int j = maxWeight; j >= weights[i]; j--) {
      int takeValue = values[i] + ans[j - weights[i]];
      if (takeValue > ans[j]) {
        ans[j] = takeValue;
      }
    }
  }
  return ans[ans.length - 1];
}

完全背包：

public static int unpack(int[] values, int[] weights, int maxWeight) {
  int[] ans = new int[maxWeight + 1];
  for (int i = 0; i < values.length; i++) {
    for (int j = weights[i]; j <= maxWeight; j++) {
      int takeValue = values[i] + ans[j - weights[i]];
      if (takeValue > ans[j]) {
        ans[j] = takeValue;
      }
    }
  }
  return ans[maxWeight];
}