题意：
给定一堆硬币，然后将他们分成两部分，使得两部分的差值最小;输出这个最小的差值。
思路：
想了好久都没想到一个合适的状态转移方程。后面看了别人的题解后，才知道能够转成背包问题求解。
我们将全部的硬币和的一半作为背包容量，然后将硬币的代价看成其本身的面值。然后背包中能装的最大容量
就是当中一个人分得硬币数。
代码例如以下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int i,j,k,t; scanf("%d",&t); while(t--) { int m,a[110],dp[100000],sum=0; memset(dp,0,sizeof(dp)); scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&a[i]); sum+=a[i]; } int V=sum/2; for(i=1;i<=m;i++) for(j=V;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+a[i]); printf("%d\n",sum-2*dp[V]); } return 0; }
转载于:https://www.cnblogs.com/bhlsheji/p/4296113.html
相关资源：数据结构—成绩单生成器