leetcode - knapsack dp - 1049. Last Stone Weight II

1049. Last Stone Weight II (weekly 137)

1. Given an integer (stone) array, separate the integers into two sets, named A, B
2. return the minimum value of Sum(A) - Sum(B)

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 100

Reference from committed code.

Very smart.

int lastStoneWeightII(vector<int>& stones) {
  constexpr int MAX = 3000 / 2 + 100 + 1;
  bitset<MAX> possibleSum;
  possibleSum[0] = true;

  for (int s : stones)
    possibleSum = possibleSum | (possibleSum << s);

  int total = accumulate(stones.begin(), stones.end(), 0);

  // find left partition.
  int leftPart = 0;
  for (int i = total / 2; i >= 0; --i)
    if (possibleSum[i]) {
      leftPart = i;
      break;
    }

  // find right partition.
  int rightPart = 0;
  for (int i = (total + 1) / 2; i <= total; ++i)
    if (possibleSum[i]) {
      rightPart = i;
      break;
    }

  return rightPart - leftPart;
}

by neal_wu's contest solution.

int lastStoneWeightII(vector<int>& stones) {
    int n = stones.size();
    vector<bool> possible(2 * MAX + 1, false);
    possible[MAX] = true;

    for (int stone : stones) {
        vector<bool> next_possible(2 * MAX + 1, false);

        for (int x = 0; x <= 2 * MAX; x++)
            if (possible[x])
                next_possible[x + stone] = next_possible[x - stone] = true;

        possible = next_possible;
    }

    for (int i = 0; i <= MAX; i++)
        if (possible[MAX + i])
            return i;

    return -1;
}

leetcode - knapsack dp

956. Tallest Billboard

1. Given an integer array, separate these numbers (don't have to use all numbers) into 2 sets, named A and B.
2. Sum(A) = Sum(B)
3. Find the maximum sum.

Note: The sum of rods is at most 5000.

Example:

(a) [1,2], max sum = 0.
(b) [1,2,3,4,5,6], max sum = 10, can separate into {2, 3, 5} and {4, 6}

12 ms version, sampled from committed solution:

// left/right is billboard height of each side
// index points to next rod
void dfs_12ms(vector<int> &rods, int left, int right,
              int remain, int index,
              int &result)
{
  if (abs(left - right) > remain ||
      left + right + remain <= result * 2)
    return;

  if (left == right && result < left)
    result = left;

  if (index == rods.size())
    return;

  remain -= rods[index];
  dfs_12ms(rods, left + rods[index], right, remain, index + 1, result);
  dfs_12ms(rods, left, right + rods[index], remain, index + 1, result);
  dfs_12ms(rods, left, right, remain, index + 1, result);
}

int tallestBillboard_12ms(vector<int> &rods) {
  sort(rods.begin(), rods.end(), greater<int>());
  int sum = 0;
  for (const auto &r : rods)
    sum += r;

  int result = 0;
  dfs_12ms(rods, 0, 0, sum, 0, result);
  return result;
}

// ref: https://leetcode.com/problems/tallest-billboard/discuss/203274/Simple-C%2B%2B-DP-beating-100-O(NM)#_=_
// 28 ms (CY 2nd attempt)
bool isValid(int s) const { return s >= 0; }

int tallestBillboard(vector<int>& rods) {
  if (rods.empty())
    return 0;

  int maxsum = accumulate(rods.begin(), rods.end(), 0) / 2;
  const int n = rods.size();
  
  // dp[i][diff]: The maximum pair of s0 and s1 from
  // set of {rods[j], j <= i} which has difference = diff
  //
  // s1 is always s0, so dp[i][diff] = s0 + diff = s1
  //vector<vector<int>> dp(n + 1, vector<int>(maxsum + 1));
  
  int dpPrevData[maxsum + 1];
  int dpCurData[maxsum + 1];
  
  int *dpPrev = dpPrevData;
  int *dpCur = dpCurData;
  
  for (int i = 1; i <= maxsum; i++)
    dpPrev[i] = -1;
  dpPrev[0] = 0;

  for (int i = 1; i <= n; ++i) {
    int rodi = rods[i - 1];
    for (int j = 0; j <= maxsum; ++j) {
      /// case a: Do not use rodi.
      int a = dpPrev[j];
      
      /// case b: Add rodi to s1.
      int b = -1;
      if (j >= rodi && isValid(dpPrev[j - rodi]))
        b = dpPrev[j - rodi] + rodi;
      
      /// case c: Add rodi to s0, but s1 is still greater than s0.
      int c = -1;
      if (j + rodi <= maxsum) // rodi > j )
        c = dpPrev[j + rodi];

      /// case d: Add rodi to s0, but s0 is now greater than s1,
      ///         and will be swapped.
      int d = -1;
      if (rodi > j && rodi - j <= maxsum && isValid(dpPrev[rodi - j]))
        d = dpPrev[rodi - j] + j;
      
      dpCur[j] = max({a, b, c, d});
    }
    swap(dpCur, dpPrev);
  }

  return dpPrev[0];
}