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 <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define CLR(c,v) (memset(c,v,sizeof(c)))
using namespace std;template <typename _T>
inline _T Max(_T a,_T b)
{return (a>b)?(a):(b);
}
template <typename _T>
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<n_bags; ++i)  // max:1000{scanf("%d",&value[i]);sum_cost+=value[i];}int mid_cost=sum_cost/2;for(int i=0; i<n_bags; ++i){for(int j=mid_cost; j>=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 input
3
3
2 3 5
4
1 2 4 6
4
1 4 5 6
sample ouput
0
1
2
*/

这篇关于UVA 562 Dividing coins （01背包基础）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---