description:
有n个苹果 分给两个人 要求两个人所得苹果质量之间差距最小 苹果不能被拆分
solution:
最理想的状态是两边均分 根据其没办法拆分的特性 把均分的质量作为背包的容量 这样问题就转换成背包最大容量是多少了
跑一遍背包即可
code:
#include <bits/stdc++.h> using namespace std; int w[205]; int f[10005]; int main(){ int n; cin >> n; int sum = 0; for(int i = 1;i <= n;i ++){ cin >> w[i]; sum += w[i]; } int t = sum / 2; for(int i = 1;i <= n;i ++){ for(int j = t;j >= w[i];j --){ f[j] = max(f[j - w[i]] + w[i],f[j]); } } cout << f[t] << ' ' << sum - f[t] << '\n'; return 0; }