# 1163. easy to do DP

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;
}

//状态：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为什么加了限制就A不了，怎么修枝剪叶

### include

using namespace std;
int n;
int a[25];
long long Min=1e18;
int ans=0;
void dfs(int pos,long long sum) {
if(pos==n) {
Min=min(Min,abs(ans-2sum));
return;
}
//if(abs(ans-2
sum-2*a[pos])>n) {
ans=0;
for(int i = 0; i < n; i++) {
cin>>a[i];
ans+=a[i];
}
Min=1e18;
dfs(0,0);
cout<<Min<<endl;
}
return 0;
}