首页 > ACM题库 > 九度OJ > 九度-1420-Jobdu MM分水果[解题代码]
2013
12-13

九度-1420-Jobdu MM分水果[解题代码]

题目描述:

Jobdu团队有俩PPMM,这俩MM干啥都想一样。一天,富强公司给团队赞助了一批水果,胡老板就把水果派发给了这俩MM,由她们自行分配。每个水果都有一个重量,你能告诉她们怎么分才使得分得的重量差值最小吗?

输入:

        输入有多组数据,每组数据第一行输入水果个数n(1<=n<=100),接下来一行输入n个重量wi(0<=wi<=10^5)。

输出:

对每组输入输出一行,输出可以得到的最小差值。

样例输入:
5
10 20 30 10 10 
样例输出:
0

cpp 代码如下:
#include <stdio.h>
#include <string.h>
int n, k, a[101], v[101], t,i,m;
void dfs(int x, int y) {
	int i;
	if (y > t)
		return;
	if (y > k) {
		k = y;
	}
	if (k == t)
		return;
	for (i = x; i <= n; i++)
		if (!v[i]) {
			v[i] = 1;
			dfs(i + 1, y + a[i]);
			v[i] = 0;
		}
}
int main() {
	while(scanf("%d",&n)==1) {
		t=0;
		for(i=1;i<=n;i++) {
			scanf("%d",a+i);t+=a[i];
		}
		k=-1;m=t;t/=2;memset(v,0,sizeof(v));
		dfs(1,0);
		printf("%d\n",m-k*2);
	}}
/**************************************************************
	Problem: 1420
	User: coder
	Language: C
	Result: Accepted
	Time:50 ms
	Memory:916 kb
****************************************************************/


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

      • 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。