标签存档: 动态规划

0/1背包和完全背包的java解法

作者: 日期: 2009年07月14日 没有评论

背包问题：

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

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

思路：推荐

说的清清楚楚地。

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

  1. public static int unpack(int[] values, int[] weights, int maxWeight) {
  2.   int[] ans = new int[maxWeight + 1];
  3.   for (int i = 0; i < values.length; i++) {
  4.     for (int j = maxWeight; j >= weights[i]; j--) {
  5.       int takeValue = values[i] + ans[j - weights[i]];
  6.       if (takeValue > ans[j]) {
  7.         ans[j] = takeValue;
  8.       }
  9.     }
  10.   }
  11.   return ans[ans.length - 1];
  12. }

完全背包：

  1. public static int unpack(int[] values, int[] weights, int maxWeight) {
  2.   int[] ans = new int[maxWeight + 1];
  3.   for (int i = 0; i < values.length; i++) {
  4.     for (int j = weights[i]; j <= maxWeight; j++) {
  5.       int takeValue = values[i] + ans[j - weights[i]];
  6.       if (takeValue > ans[j]) {
  7.         ans[j] = takeValue;
  8.       }
  9.     }
  10.   }
  11.   return ans[maxWeight];
  12. }