vector<vector<int>> memo;
vector<int> arr;
int dp(int w, int n){
if (w == 0) return 0;
if (n == 0) return 1e8;
int &ans = memo[w][n];
if (ans != -1) return ans;
ans = 1e8;
if (arr[n] > w) ans = dp(w, n-1);
else{
int include = 1 + dp(w - arr[n], n-1);
int exclude = dp(w, n-1);
ans = min(include, exclude);
}
return ans;
}
int Solution::solve(const vector<int> &A) {
int n = A.size();
if (n == 1) return 0;
if (n == 2){
if (A[0]*A[1] > 0) return 1;
else return 0;
}
vector<int> sortedA = A;
sort(sortedA.begin(), sortedA.end());
int total = 0;
for (int x: sortedA) total += x;
int capacity = total/2;
memo.assign(capacity+1, vector<int>(n+1, -1));
arr = A;
return dp(capacity, n-1);
}