老王土偏方

动态规划

我们只考虑其中一个人,因为另一个人可以通过第一个人直接求出。

令dp[i][j]表示考虑到第i个物品时有没有总和为j的方案。

dp[i+1][j+a[i]]=1,dp[i+1][j]=1

最后如果dp[n+1][x]=1且dp[n+1][totalsum-x]=1那么x,totalsum-x就是一组可行解。

取min即可。