【题目大意】给定n种食材，每种食材有酸度a_i和甜度b_i。可以选择若干食材放入料理，要求料理的总酸度A等于总甜度B，并且在满足这个条件的前提下，最大化A+B的值。需要计算这个最大的A+B值。(1≤n ≤100，1≤a_i,b_i≤500）

【考纲知识点】

简单动态规划（一维动态规划、简单背包问题）

【解题思路】

问题转化：本质上是一个变种的背包问题，需要找到一组食材，使得它们的总酸度和总甜度相等，并且这个总和的2倍（因为A+B=A+A=2A）尽可能大。

动态规划：使用动态规划来记录可能的酸度和甜度差值。定义dp[i][j]表示前i种食材，酸度与甜度的差值为j时，能达到的最大总酸度（或总甜度）。

状态转移：对于每种食材，考虑选或不选：

不选：状态不变。

选：更新差值j和总酸度。

初始状态：dp[0][0] = 0，表示初始时差值为0，总和为0。

目标状态：dp[n][0]

【参考程序】
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 105;
const int C = 505;
const int OFFSET = N * C;  // 偏移量，用于处理负索引
const int D = 2 * OFFSET;  // 数组总大小

int n;
int f[D];

int main() {
    scanf("%d", &n);
    // 初始化数组，设置一个极小值表示不可达状态
    for (int i = 0; i < D; i++)
        f[i] = -1e9;
    // 初始状态：选择0种食材时，差值为0，贡献和为0
    f[OFFSET] = 0;
    
    while (n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int x = a + b;  // 该食材的总贡献
        int y = a - b;  // 该食材的酸甜差值
        
        if (y <= 0) {
            // 处理非正差值，从左到右遍历，避免重复使用同一食材
            // 限制遍历范围，确保i + y在有效范围内
            for (int i = -y; i < D; i++) {
                if (f[i] != -1e9) {  // 只处理可达状态
                    f[i + y] = max(f[i + y], f[i] + x);
                }
            }
        } else {
            // 处理正差值，从右到左遍历，避免重复使用同一食材
            // 限制遍历范围，确保i在有效范围内
            for (int i = D - 1; i >= y; i--) {
                if (f[i - y] != -1e9) {  // 只处理可达状态
                    f[i] = max(f[i], f[i - y] + x);
                }
            }
        }
    }
    
    // 输出差值为0时的最大贡献和，如果不可达则输出0
    printf("%d\n", max(f[OFFSET], 0));
    return 0;
}

第二种方法：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 105;
const int M = 100000;   // 差值范围[-50000,50000]
const int base = 50000;   // 偏移量

int n;
int a[N], b[N];
int f[105][100005];   // f[i][j]：前i个食材，差值（加上偏移量）为j的最大总和。

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
    }

    memset(f, -0x3f, sizeof(f));
    f[0][base] = 0;

    for (int i = 1; i <= n; i++) {
        int d = a[i] - b[i];
        int s = a[i] + b[i];
        for (int j = 0; j <= M; j++) {
            f[i][j] = f[i-1][j];   // 不选第i个
            if (j - d >= 0 && j - d <= M) {
                f[i][j] = max(f[i][j], f[i-1][j-d] + s);
            }
        }
    }

    printf("%d\n", f[n][base] > 0 ? f[n][base] : 0);
    return 0;
}