5-分西瓜差最小（背包 || dfs）

/*   zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难题，never和C小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？

输入
    多组测试数据（<=1500）。数据以EOF结尾
    第一行输入西瓜数量N (1 ≤ N ≤ 20)
    第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量
输出
    输出分成两堆后的质量差
样例输入

5
    5 8 13 27 14

样例输出

3
*/

方法一：可以转为背包：
//差距最小肯定是越接近一半是最好的，转化为01背包

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int p[100025];

int a[100025];  //题目太坑了，不是说了0~20吗，但非要开这个数量级才能过

int main(){

    int n;

    while(scanf("%d", &n) != EOF){

        memset(p, 0, sizeof(p));   //每次撒比的忘记清零

        double sum = 0;

        for(int i = 0; i < n; i++){

            scanf("%d", &a[i]);

            sum += a[i];

        }

        int v = sum / 2;

        for(int i = 0; i < n; i++){

            for(int j = v; j >= a[i]; j--)

                if(p[j - a[i]] + a[i] > p[j])

                    p[j] = p[j - a[i]] + a[i];

        }

        printf("%d\n", ((int)sum - p[v] * 2));

        /*sum为double型 %d 不能输出 printf除了第一个参数，后面的是void*型的，可以为任何类型数据。

        但是在执行printf函数时，先把所有参数按从右向左的顺序压入堆栈，参数进入堆栈后就是连续储存了，然后再按照printf第一个参数的格式来处理数据，

        由于数据连续，所以只要前面一个数据没有对齐，后面的都会出错。用“%d”来输出double型的数据，相当于丢弃了四个字节，这被丢弃的四个字节就被

        归到后面的数据去了，有可能就会导致后面的数据出错 */

    }

    return 0;

}

　　方法二：dfs

#include <iostream>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <cstdio>

using namespace std;

int gua[22];

int mincha;

int n;

int maxsum;

void dfs(int k, double ma){ //目前在k的位置往后搜, 和为ma

	if(k == n)

		return ;

	if(abs(maxsum - ma * 2) < mincha){

		mincha = abs(maxsum - 2 * ma);

	}

	dfs(k + 1, ma + gua[k + 1]); //分为两种情况，第k + 1个元素放进去和不放进去

	dfs(k + 1, ma);

}

int main(){

	while(scanf("%d", &n) == 1){

		mincha = 0x3fffffff;

		maxsum = 0;

		for(int i = 0; i < n; i++){

			scanf("%d", &gua[i]);

			maxsum += gua[i];

		}

		dfs(0, 0);

		printf("%d\n", mincha);

	}

	return 0;

}