题目大意：已知c[i]...c[n]及f[i]...f[n]，现要选出一些i，使得当sum{c[i]}和sum{f[i]}均非负时，sum(c[i]+f[i])的最大值。
以sum(c[i])（c[i]>=0）作为背包容量totV，i当作物体，c[i]当作物体体积，f[i]当作物体重量，01背包后,求max{j+DP[j]} （非负）即可。
注意：
- 这里物体体积存在负数，所以循环j时起始条件不能为j=0！而应当在for下面加if，判断子问题在minJ~maxJ范围之内。
- 初值不是DP[最左端点]=0，而是DP[0点所在位置]=0。
#include#include #include using namespace std;const int MAX_V = 200010, MAX_OBJ = 110;#define M(x) x+offset//moveint DP(int minJ, int maxJ, int totObj, int *_v, int *_w){ static int DP[MAX_V]; int offset = max(-minJ, 0); memset(DP, 0xcf, sizeof(DP)); DP[M(0)] = 0; for (int i = 1; i <= totObj; i++) { if (_v[i] <= 0) { for (int j = minJ; j <= maxJ; j++) if (j >= minJ + _v[i] && j <= maxJ + _v[i]) DP[M(j)] = max(DP[M(j)], DP[M(j - _v[i])] + _w[i]); } else { for (int j = maxJ; j >= minJ; j--) if (j >= minJ + _v[i] && j <= maxJ + _v[i]) DP[M(j)] = max(DP[M(j)], DP[M(j - _v[i])] + _w[i]); } } int ans = 0; for (int j = 0; j <= maxJ; j++) if(DP[M(j)] >=0) ans = max(ans, j+DP[M(j)]); return ans;}int main(){#ifdef _DEBUG freopen("c:\\noi\\source\\input.txt", "r", stdin);#endif static int _s[MAX_OBJ], _f[MAX_OBJ]; int n, minS = 0, maxS = 0, cnt = 0, s, f, tempAns = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &s, &f); if (s >= 0 && f >= 0) { tempAns += s + f; continue; } else if (s <= 0 && f <= 0) continue; else { cnt++; _s[cnt] = s; _f[cnt] = f; _s[cnt] > 0 ? maxS += _s[cnt] : minS += _s[cnt]; } } printf("%d\n", tempAns + DP(minS, maxS, cnt, _s, _f)); return 0;}