Untitled
unknown
c_cpp
a year ago
895 B
2
Indexable
Never
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); }