题目描述

给定一组石头，每个石头有一个正数的重量。每一轮开始的时候，选择两个石头一起碰撞，假定两个石头的重量为x，y，x<=y,碰撞结果为
1. 如果x==y，碰撞结果为两个石头消失
2. 如果x != y，碰撞结果两个石头消失，生成一个新的石头，新石头重量为y-x

最终最多剩下一个石头为结束。求解最小的剩余石头质量的可能性是多少。

输入描述

第一行输入石头个数(<=100)

第二行输入石头质量，以空格分割，石头质量总和<=10000

输出描述

最终的石头质量

示例

输入

6
2 7 4 1 8 1

输出

1

0-1 背包

这道题长得有点像 石子合并 那道题,
但是并不是, 这里并没有强调是相邻的两个石子合并, 而是可以随机的挑选。

由题意可以知道, 其实可以分为两堆石子, 一堆的石子作为被减数(正数), 另一堆的石子作为减数;
而想要 这两堆石子尽可能的接近, 必然需要有一堆石子是不超过总石子重量的一半。

我们找到 不超过总石子重量一半 的那堆石子的可能组合 –> 给定一个物件,每个物件有其重量, 找到不小于总背包容量(总石子重量的一半)的 所有合法组合 –> 就变成了0-1背包的问题(求具体方案)

最后在所有可能的组合中 挑选最符合题意(最大的)的那一堆石子即可。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 110, M = 10010;

int a[N];
int sum; 
bool f[M]; 
int n;

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++)
        cin >> a[i], sum += a[i];

    f[0] = true; // f[j] 表示容量 恰好 为j的组合是可行的。
    for(int i = 1; i <= n; i ++)
        for(int j = sum/2; j >= a[i]; j --)
            f[j] |= f[j - a[i]]; // 只有恰好 容量是j 才是合法的(必须从f[0]转移过来)

    int res;     
    for(int i = sum/2; i >= 0; i --)
        if(f[i])
        {   
            res = abs(i - (sum - i)); 
            break;
        } // 找到最大的即可

    cout << res << endl;
    return 0;
}