当女朋友说这个618要凑单买……

我们先来解决个简单的问题，假设现在杂货铺有 5 件商品参与这个优惠，且价格分别为31、26、31、21、40，优惠商品限购一件，那么女朋友在预算范围内，最多能花多少钱？

面对这个问题，我们首先可以想到的解决方法就是穷举出所有的商品组合，然后找出预算范围内的最大值。这个真的很暴力，假如小卖部上架了百万个商品， 那这运算的电脑怕是要崩了……

那么这是不是有更加优雅的解决方式呢？

其实在凑单的过程中，我们一直在一件事，就是看到一个商品的时候，判断要不要放到购物车中，加入购物车以后总价变大，不加的话，总价自然不会变化。当一件商品确定要不要加入购物车以后，我们再判断下一件商品的，这种操作有一个专业的名词，就是动态规划，用这个词用来表达，这逼格是不是高大上了很多。

我们用 i 表示第几个商品，用 j 表示第 i 件商品决定加不加购物车以后，购物车总价的变化。i 和 j 的组合，(i,j)就可以表示一种操作之后的状态，如果这种操作状态存在，我们就设置为 true，否则就是false。

然后我们根据这个操作的过程画出这个流程。

我们可以看出这只是前三个商品选择的所有可能性，从这个树状图我们可以看到，虽然只操作了三个商品，但是已经有重复的状态出现， 可见当我们穷举的时候，多做了多少无用功。

但是当操作同一件物品的时候，出现同样的状态时，是不会重复的。多说无用，直接上代码。

参考代码

int[] item = {21, 26, 31, 21, 40}; // 每件商品对应的价格
int n = 75; // 预算限制
int len = item.length;
boolean[][] status = new boolean[len][n + 1]; // 记录操作第几件商品之后的状态
status[0][0] = true; // 设置不选择第一件商品之后的状态
status[0][item[0]] = true; // 设置选择第一件商品之后的状态
for (int i = 1; i < len; i++) { // 从第二件商品之后开始操作
  for (int j = 0; j <= n; j++) { // 不选择当前商品时状态变化
    if (status[i - 1][j] == true) // 只有当上一个商品的操作状态存在时，我们才能进行下一步操作
      status[i][j] = true;
  }
  for (int j = 0; j <=n - item[i]; j++) { // 设置选择当前商品后的状态变化
    if (status[i - 1][j] == true) {
      status[i][j + item[i]] = true;
    }
  }
}
// 获取运算之后的结果
for (int k = n; k >= 0; k--) { 
  if (status[len - 1][k] == true) {
    System.out.println(k);
    break;
  }
}

注意！注意！注意！！！这里设置了第一商品的状态，这里有什么玄机吗？第一个加入购物车的商品，在它之前没有任何可以参考的状态，假如我们不设置的话，在循环里面的操作就会报错，我们就要在循环里面判断这个商品是第几个，这样就增加了循环体内的操作。

我们设置第一个商品操作后的状态，这样就保证了边界安全性。这种操作的专业名词叫做哨兵机制，边界哨兵，是不是充满了逼格。

在处理问题的时候，提前设置好边界的值，防止遇到边界问题，以及减少循环内的判断，可以提高代码运行效率。

兄弟们，你以为这样就可以优雅结束了吗？

不，这才是个开始。

就目前这个操作来说，我们要关注的点只有价格的变化，那么这是不是意味着我们可以忽略掉记录第一个物品的 i 呢?

如果我们要忽略掉它，那么我们要怎么记录两种状态的变化呢？

仔细想，当我们没有把第 i 件商品添加到购物车中时，价格是没有变化的，这就意味着，这种价格的状态就是上一个商品操作后的状态，我们就不需要重复记录没有添加商品的状态，因此我们只要记录添加当前物品添加购物车以后引起的价格的变化即可。

代码参考

int[] item = {21, 26, 31, 21, 40}; 
int n = 75;
int len = item.length;
boolean[] status = new boolean[n + 1];
status[0] = true;
status[item[0]] = true;
for (int i = 1; i < len; i++) {
  for (int j = n - item[i]; j >= 0; j--) {
    if (status[j] == true) {
      status[j + item[i]] = true;
    }
  }
}
for (int k = n; k >= 0; k--) {
  if (status[k] == true) {
    System.out.println(k);
    break;
  }
}

这段代码的复杂度很容易可以看出来，与物品的数量(len)和价格(n)有关，也就是O(len*n)

注意看，这里的代码略有不同，价格 j 是递减变化的，想一想这是为什么呢？