存在负数的背包问题

题目1

体积和价值可能为负数的01背包。

Solution

逆向思维，对于体积为负的物品，我们可以一开始就装进去，背包对应的进行扩容，物品的体积和价值也对应取反。这样在进行背包dp 的时候就代表移除这个物品，答案取最大值即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 410;
int c[N], v[N], ans;
int dp[40010];
int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) {
    scanf("%d%d", &c[i], &v[i]);
    if (c[i] <= 0) {
      ans += v[i];
      M -= c[i];
      c[i] = -c[i];
      v[i] = -v[i];
    }
  }
  for (int i = 1; i <= N; i++)  
    for (int j = M; j >= c[i]; j--) dp[j] = max(dp[j], dp[j - c[i]] + v[i]);

  for (int i = 0; i <= M; i++) {
    dp[M] = max(dp[M], dp[i]);
  }
  printf("%d\n", ans + dp[M]);
  return 0;
}

题目2

体积和价值可能为负数且要求所取的物品体积之和和价值之和都大于0的条件下，两者总和最大的01背包。$(n = 100, -1000<=v,w<=1000)$

Solution

由于体积可能为负，因此需要负数转化为正数，以 $100000$ 为分界线划分为左边代表正数，右边代表负数做背包dp即可，当体积为负时，转移是由大的容量转移过来，需要从小到大遍历。最后取分界线右侧且dp值大于 0 的体积加价值最大值即可。

Code

#include <iostream>
using namespace std;
const int m = 2e5 + 5;
int n, x, y, res, dp[m];
int main() {
  cin >> n;
  for (int i = 0; i < m; i++) dp[i] = -m;
  dp[100000] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> x >> y;
    if (x >= 0) {
      for (int j = m - 1; j >= x; j--) {
        if (dp[j - x] != -m) dp[j] = max(dp[j], dp[j - x] + y);
      }
    } else {
      for (int j = 0; j < m + x; j++) {
        if (dp[j - x] != -m) dp[j] = max(dp[j], dp[j - x] + y);
      }
    }
  }
  for (int i = 100000; i < m; i++) {
    if (dp[i] > 0) res = max(res, dp[i] + i - 100000);
  }
  cout << res << endl;
  return 0;
}