题解：01背包

题目可以抽象为有$n$个物品，第$i$个物品的体积为$a[i]$，价值为$a[i]$，设总体积为$V$，问是否有一种选择方式，可以使得选择若干个物品（每个物品最多只能被选择一次），使得所选物品总体积恰好为$\frac{V}{2}$

首先，如果所有物品的总体积之和$V$为奇数，则一定不满足条件，输出0即可

我们按照动态规划的三要素来分析这道题：状态方程定义、状态初始化、状态转移方程

状态方程定义

我们定义$f[i][j]$为选择前$i$个物品，所选物品总体积恰好为$j$的情况是否存在

显然，最终的答案即为$f[n][\frac{V}{2}]$

状态初始化

我们定义数组下标从1开始，一开始什么数字都不选，和为0，因此有$f[0][0]=1$（表示空数组的情况）

状态转移方程

当我们枚举到第$i$个物品，有两种情况：选择或者是不选择

由于答案不是0就是1，因此可以使用|运算符来进行计算。

• 如果不选择第$i$个物品，则有$f[i][j] \;|=f[i-1][j]$
• 如果选择第$i$个物品，则有$f[i][j]\;|=f[i-1][j-a[i]]$

由于$f[i][j$只与$f[i-1][j]$和$f[i-1][j-a[i]]$这两个状态有关，因此可以使用滚动数组，将空间复杂度优化至$O(total)$，大家可以学习一下这两种写法。

C++(朴素版)

#include <bits/stdc++.h>
using namespace std;
const int N=1E3+10,M=2E3+10;
int n,a[N],f[N][M];
int main()
{
    int x,total=0;
    while(cin>>x){
        if(n==0){  //跳过第一个数字
            n=1;
            continue;
        }
        a[n++]=x;  //下标从1开始
        total+=x;
    }
    n--;
    if(total%2){  //总和为奇数,一定不存在合法方案
        puts("0");
    }
    else{
        f[0][0]=1;
        total/=2;
        for(int i=1;i<=n;i++){
            for(int j=a[i];j<=total;j++){
                f[i][j]|=f[i-1][j];  //不选择第i个数字
                f[i][j]|=f[i-1][j-a[i]];  //选择第i个数字
            }
        }
        cout<<f[n][total]<<endl;
    }
    return 0;
}

Java(朴素版)

import java.util.Scanner;

public class Main {
    private static final int N = 1000 + 10;
    private static final int M = 2000 + 10;
    private static int[] a = new int[N];
    private static int[][] f = new int[N][M];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = 0;
        int n = 0;
        while (scanner.hasNextInt()) {
            int x = scanner.nextInt();
            if (n == 0) {  // 跳过第一个数字
                n = 1;
                continue;
            }
            a[n++] = x;  // 下标从1开始
            total += x;
        }
        n--;
        if (total % 2 != 0) {  // 总和为奇数,一定不存在合法方案
            System.out.println("0");
        } else {
            f[0][0] = 1;
            total /= 2;
            for (int i = 1; i <= n; i++) {
                for (int j = a[i]; j <= total; j++) {
                    f[i][j] |= f[i - 1][j];  // 不选择第i个数字
                    f[i][j] |= f[i - 1][j - a[i]];  // 选择第i个数字
                }
            }
            System.out.println(f[n][total]);
        }
    }
}

Python(朴素版)

a=list(map(int,input().split()))
n=a[0]
total=sum(a)-n  #计算总和
f=[[0] * (total+1) for _ in range(n+1)]
if total % 2:  # 总和为奇数,一定不存在合法方案
    print("0")
else:
    f[0][0] = 1
    total //= 2
    for i in range(1, n + 1):
        for j in range(a[i], total + 1):
            f[i][j] |= f[i - 1][j]  # 不选择第i个数字
            f[i][j] |= f[i - 1][j - a[i]]  # 选择第i个数字
    print(f[n][total])

C++(滚动数组优化版)

#include <bits/stdc++.h>
using namespace std;
const int N=1E3+10,M=2E3+10;
int n,a[N],f[M];
int main()
{
    int x,total=0;
    while(cin>>x){
        if(n==0){  //跳过第一个数字
            n=1;
            continue;
        }
        a[n++]=x;  //下标从1开始
        total+=x;
    }
    n--;
    if(total%2){  //总和为奇数,一定不存在合法方案
        puts("0");
    }
    else{
        f[0]=1;
        total/=2;
        for(int i=1;i<=n;i++){
            for(int j=total;j>=a[i];j--){
                f[j]|=f[j-a[i]];
            }
        }
        cout<<f[total]<<endl;
    }
    return 0;
}

Java(滚动数组优化版)

import java.util.Scanner;

public class Main {
    private static final int N = 1000 + 10;
    private static final int M = 2000 + 10;
    private static int[] a = new int[N];
    private static int[] f = new int[M];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = 0;
        int n = 0;
        while (scanner.hasNextInt()) {
            int x = scanner.nextInt();
            if (n == 0) {  // 跳过第一个数字
                n = 1;
                continue;
            }
            a[n++] = x;  // 下标从1开始
            total += x;
        }
        n--;
        if (total % 2 != 0) {  // 总和为奇数,一定不存在合法方案
            System.out.println("0");
        } else {
            f[0] = 1;
            total /= 2;
            for (int i = 1; i <= n; i++) {
                for (int j = total; j >= a[i]; j--) {
                    f[j]|=f[j-a[i]];
                }
            }
            System.out.println(f[total]);
        }
    }
}

Python(滚动数组优化版)

a=list(map(int,input().split()))
n=a[0]
total=sum(a)-n  #计算总和
f=[0] * (total+1) 
if total % 2:  # 总和为奇数,一定不存在合法方案
    print("0")
else:
    f[0] = 1
    total //= 2
    for i in range(1, n + 1):
        for j in range(total,a[i]-1,-1):
            f[j]|=f[j-a[i]]
    print(f[total])