UVA 562 Dividing coins （01背包基础）

UVA 562 Dividing coins （01背包基础）

【题目链接】：​​click here~~​​

代码：

/** Problem: UVA No.562* Running time: 0MS* Complier: C++* Author: ACM_herongwei* Create Time: 11:12 2015/9/9 星期三* zeroonebags * 将金币总价值的一半作为背包容量，然后zeronebags*/#include #include #include #include #define CLR(c,v) (memset(c,v,sizeof(c)))using namespace std;template inline _T Max(_T a,_T b){ return (a>b)?(a):(b);}template inline _T Maxx(_T a,_T b,_T c){ return (a>Max(b,c))?(a):(Max(b,c));}const int N = 1e5 + 10;int dp[N];int value[N];int main(){ int Ncase; scanf("%d",&Ncase); while(Ncase--) { CLR(dp,0); int sum_cost=0, n_bags; scanf("%d",&n_bags); for(int i=0; i=value[i]; --j) { if(dp[j]<=dp[j-value[i]]+value[i]) { dp[j]=dp[j-value[i]]+value[i]; } } } printf("%d\n",sum_cost-2*dp[mid_cost]); } return 0;}/*sample input332 3 541 2 4 641 4 5 6sample ouput012*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。