灵异背包？

思路

拿到这题先想想：给你一堆正整数，选若干个放背包里，要求总和是偶数，还要尽可能大。那第一反应是什么？

全选不就最大了吗？

对，先把所有正整数加起来。如果总和本身就是偶数，那直接就是答案，完事。

那要是总和是奇数呢？想想什么时候总和会是奇数——一定是奇数个奇数的贡献。那我们只要"去掉"一个奇数，总和的奇偶性就翻转成偶数了。为了让结果尽可能大，我们应该去掉哪个？当然是最小的那个奇数。

特殊情况

还有一种边界：如果所有数都是奇数且只有一个，总和是奇数，去掉它之后就是 0。题目说"一个数也不选，则背包和为 0"，而 0 是偶数，所以输出 0 就行。

总结一下策略

  1. 把所有正整数求和，同时记录最小的奇数
  2. 如果总和是偶数，直接输出
  3. 如果总和是奇数，减去最小的奇数再输出

就这么简单，贪心的核心就是：全都要，实在不行就丢最小的奇数。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    long long sum=0;
    long long minOdd=LLONG_MAX;
    for(int i=0;i<n;i++){
        long long x;
        scanf("%lld",&x);
        if(x>0){
            sum+=x;
            if(x%2==1) minOdd=min(minOdd,x);
        }
    }
    if(sum%2==1){
        sum-=minOdd;
    }
    printf("%lld\n",sum);
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long sum=0;
        long minOdd=Long.MAX_VALUE;
        for(int i=0;i<n;i++){
            long x=sc.nextLong();
            if(x>0){
                sum+=x;
                if(x%2==1) minOdd=Math.min(minOdd,x);
            }
        }
        if(sum%2==1){
            sum-=minOdd;
        }
        System.out.println(sum);
    }
}

n = int(input())
a = list(map(int, input().split()))
s = 0
min_odd = float('inf')
for x in a:
    if x > 0:
        s += x
        if x % 2 == 1:
            min_odd = min(min_odd, x)
if s % 2 == 1:
    s -= min_odd
print(s)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let sum = 0;
    let minOdd = Infinity;
    for (const x of a) {
        if (x > 0) {
            sum += x;
            if (x % 2 === 1) minOdd = Math.min(minOdd, x);
        }
    }
    if (sum % 2 === 1) {
        sum -= minOdd;
    }
    console.log(sum);
});

复杂度分析

  • 时间复杂度: ，遍历一遍数组即可
  • 空间复杂度: ，只用了常数个变量

总结

这题名字叫"灵异背包"，但其实跟传统背包问题没啥关系，不需要动态规划。关键在于想清楚贪心策略：先全选拿最大和，如果和是奇数就减掉最小的奇数让它变偶数。一个 for 循环搞定，属于贪心入门的好题。