Google – Get Some Beer

Google – Get Some Beer
有三台接啤酒的机器，分别是small, medium, large。三种size的机器按一次分别能distribute一定范围的啤酒，比如
small的能接[100, 150]ml
medium的能接[200, 300]ml
large的能接[300, 350]ml
问题是如果一个顾客拿一个范围在[minVolume, maxVolume]的杯子去接啤酒，意思就是必须接minVolume的啤酒，但不能超过maxVolume。
[Mistake]
这题其实和dp没有什么关系。本来看着挺像coin change的问题，想着用三维dp来解决，lookup[i][x][y]就表示用前i个machine是否能接到范围在[x, y]的啤酒。
但根据上面的例子，当杯子范围在[300, 400]的时候是无法用small和medium来接的，但dp的结果依然会是true。因为如果按一次medium，剩余量就是
300 – 200 = 100,
400 – 300 = 100,
而[100, 100]的范围按一次small是有可能接到的，所以会返回true。
[Solution]
其实这道题有点类似于Subset的问题，可以这么考虑，

先想清楚哪些范围是一定能接的，那么列出所有能接的范围，如果杯子不在这些范围里面，那就是接不了。

那么问题来了，哪些一定能接？
无非就是:
1 small, 2 small, … n small
1 small + 1 medium, 1 small + 2 medium … 1 small + n medium
2 small + 1 medium, 2 small + 2 medium … 2 small + n medium
…
n small + 1 medium, n small + 2 medium … n small + n medium
…
…
上面就是一个subset问题，用backtracking做就好。

class BeerMachine {

  int min;

  int max;

  BeerMachine(int min, int max) {

    this.min = min;

    this.max = max;

  }

}

class Solution {

  public boolean canGetBeer(BeerMachine[] machines, int minVolume, int maxVolume) {

    if (maxVolume < machines[0].min) {

      return false;

    }

    return backtracking(machines, 0, minVolume, maxVolume, 0, 0);

  }

  private boolean backtracking(BeerMachine[] machines, int pos, int minVolume, int maxVolume, int tmpMin, int tmpMax) {

    if (tmpMin == minVolume && maxVolume == tmpMax) {//??

      return true;

    }

    if (tmpMin > minVolume) {

      return false;

    }

    for (int i = pos; i < machines.length; i++) {

      tmpMin += machines[i].min;

      tmpMax += machines[i].max;

      if (backtracking(machines, i, minVolume, maxVolume, tmpMin, tmpMax)) {

        return true;

      }

      tmpMin -= machines[i].min;

      tmpMax -= machines[i].max;

      i++;

    }

    return false;

  }

}

Read full article from Google – Get Some Beer