uva 562Uva 562 Dividing coins

本文主要是介绍uva 562Uva 562 Dividing coins，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

平衡问题，将n个硬币的总价值累加得到sum，再用sum/2作为背包容量对n个硬币做01背包处理，看能组成的最大容量是多少。

/********************** Author:fisty* Data:2014-10-02* uva562* ******************/#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX_N 110000
int dp1[MAX_N], dp2[MAX_N];int main(){int t;scanf("%d", &t);while(t--){int n;scanf("%d", &n);int sum = 0;int v[MAX_N];for(int i = 0;i < n; i++){scanf("%d", &v[i]);sum += v[i];}int m = sum;sum = sum / 2;int u[MAX_N];memset(u, 0, sizeof(u));memset(dp1, 0, sizeof(dp1));memset(dp2, 0, sizeof(dp2));for(int i = 0;i < n; i++){for(int j = sum; j >= v[i]; j--){if(dp1[j] < dp1[j-v[i]] + v[i]){dp1[j] = max(dp1[j], dp1[j-v[i]] + v[i]);//u[i] = 1;}}}/*for(int i = 0;i < n; i++){if(!u[i]){for(int j = sum;j >= v[i]; j--){dp2[j] = max(dp2[j], dp2[j-v[i]] + v[i]);}}}*/printf("%d\n", abs(m-2*dp1[sum]));}return 0;
}

这篇关于uva 562Uva 562 Dividing coins的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---