1163. easy to do DP

//状态：dp[i][j] 前i个物品放入容量为j的背包的最大价值
//问题转换：转化为n件价值为a[i]的物品，装入容量为sum/2的背包中的最大价值
#include<iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int a[22];
int n;
int dp[22][1000020];
int main() {
    int n;
    while (cin >> n) {
        int sum = 0;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            sum = sum + a[i];
        }
        memset(dp, 0, sizeof(dp));

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= sum / 2; ++j) {
                if (j >= a[i]) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int chazhi = sum - 2 * dp[n][sum / 2];
        cout << chazhi << endl;
    }
    return 0;
}

DFS
#include <iostream>
#include <string.h>
using namespace  std;

int dp[21];
int n;
int _min = 10000000;
int sum = 0;
void DFS(int index, int sum_1) {
    if (index > n) {
        return;
    }
    if ((sum_1 * 2) >= sum) {
        int chaliang = sum_1 - (sum - sum_1);
        if (chaliang < _min) {
            _min = chaliang;
        }
        return;
    }
    DFS(index + 1, sum_1 + dp[index]);
    DFS(index + 1, sum_1);
}


int main() {
    while (cin >> n) {
        memset(dp, 0, sizeof(dp));
        sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> dp[i];
            sum = sum + dp[i];
        }
        _min = sum;
        DFS(0, 0);
        cout << _min << endl;
    }
    return 0;
}