运矿石

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
 
/**
* Welcome to vivo
*/
 
#define MAX_NUM 101
int solution(int n, int weight[]) {
    int sum=0;
    for(int i=0;i<n;i++)sum+=weight[i];
    bool f[110][10010];
    memset(f,0,sizeof(f));
    int a=0,b=0,mi=0,ans=0;
    a=(n+1)/2;
    b=(sum+1)/2;
    mi=100000;
    ans=0;
    f[0][0]=1;
    for(int i=0;i<n;i++){ 
        for(int j=sum;j>=weight[i];j--){
            for(int h=n;h>=0;h--){
                if(f[h][j-weight[i]]){
                    f[h+1][j]=1;
                    if(h+1==a){
                        if(abs(j-b)<mi){
                            mi=abs(j-b);
                            ans=j;
                        }
                    }
                }
            }
        }
    }
    return abs(sum-ans-ans);
}
 
int main()
{   
    string str("");
    getline(cin, str);
    int a[MAX_NUM];
    int i = 0;
    char *p;
    int count = 0;
     
    const char* strs = str.c_str();
    p = strtok((char *)strs, " ");
    while(p)
    {
        a[i] = atoi(p);
        count++;
        p = strtok(NULL, " ");
        i++;
        if(i >= MAX_NUM)
            break;
    }
     
    int result = solution(count, a);
    cout << result << endl;
    return 0;
}

// 有条件的背包问题，动态规划解决
int solution(int n, int weight[]) {
    int s = 0;
    for (int i = 0; i < n; ++i) {
        s += weight[i];
    }
    int S = s >> 1;
    int N = (n + 1) >> 1;
    vector<vector<int> > dp(S + 1, vector<int>(N + 1, -INF));
    for (int i = 0; i <= S; ++i) dp[i][0] = 0;
    for (int i = 0; i < n; ++i) {
        auto dp1 = dp;
        for (int j = weight[i]; j <= S; ++j) {
            for (int k = 1; k <= N; ++k) {
                dp1[j][k] = max(dp1[j][k], dp[j - weight[i]][k - 1] + weight[i]);
            }
        }
        swap(dp1, dp);
    }
    if (n & 1) {
        return s - 2 * max(dp[S][N], dp[S][N - 1]);
    }
    return s - 2 * dp[S][N];
}

//又一个三层背包问题 这个会超内存 （81%） 稍加优化一下即可
int solution(int n, int weight[]) {

    // TODO Write your code here
    int sum = 0;
    for(int i=0;i<n;i++){
        sum +=weight[i];
    }
    int CW = sum /2;
    int CN = n/2;
    vector<vector<vector<int>>> dp(n,vector<vector<int>>(CW+1,vector<int>(CN+1,0)));
    for(int j=0;j<=CW;j++){
        for(int k=0;k<=CN;k++){
            dp[0][j][k] = weight[0] <=j && 1<=k ? weight[0]:0;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<=CW;j++){
            for(int k=0;k<=CN;k++){
                dp[i][j][k] = dp[i-1][j][k];
                if(weight[i] <=j && 1<=k){
                  dp[i][j][k] = max(dp[i][j][k],weight[i] + dp[i-1][j-weight[i]][k-1]);
                }
            }
        }
    }
    return sum - 2*dp[n-1][CW][CN];

    
}

private static int solution(int[] input) {
    
    // TODO Write your code here
    int sum = 0, n = input.length;
    for (int weight : input) sum += weight;
    int rows = (n + 1) / 2, cols = sum / 2;
    int[][] dp = new int[rows + 1][cols + 1];
    // 初始化
    for (int i = 1; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dp[i][j] = Integer.MIN_VALUE;
        }
    }
    for (int i = 0; i < n; i++) {
        int weight = input[i];
        for (int j = Math.min(rows, i + 1); j > 0; j--) { // 注意
            for (int k = cols; k >= weight; k--) {
                dp[j][k] = Math.max(dp[j][k], dp[j - 1][k - weight] + weight);
            }
        }
    }
    if ((n & 1) == 0) return sum - dp[rows][cols] * 2;
    return sum - Math.max(dp[rows][cols], dp[rows - 1][cols]) * 2;
}

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
 
typedef long long ll;
 
 
const ll mod = 1e9 + 7;
const ll maxn = 2e5 + 10;
ll n,x,m;
ll a[maxn];
ll dp[2][101][10005];
ll ans;
 
 
 
int main()
{
    //freopen("input.c", "r", stdin);
    while(true){
        cin>>x;
        a[++n] = x;
        m += x;
        char ch = getchar();
        if(ch == '\n') break;
    }
    int t = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= i && j <= n/2; j ++){
            for(int k = 1; k <= m/2; k ++){
                dp[t][j][k] = max(dp[t][j][k], dp[t^1][j][k]);
                dp[t][j][k] = max(dp[t][j][k], dp[t^1][j][k-1]);
                if(k-a[i] >= 0) dp[t][j][k] = max(dp[t][j][k], dp[t^1][j-1][k-a[i]] + a[i]);
            }
        }
        t ^= 1;
    }
    t ^= 1;
    ll tmp = m - dp[t][n/2][m/2];
    ans = tmp - dp[t][n/2][m/2];
    cout<<ans<<endl;
    return 0;
}

def solution(stone_list):
    
    # 不用背包或者动态规划法
    left = stone_list[:len(stone_list) // 2]  # 将矿石分为两组
    right = stone_list[len(stone_list) // 2:]  # 数量差最多是1
    aver = sum(stone_list) / 2  # 平均重量（最终目的是让两组的重量最接近均重，这样二者差值最小，所需的砝码也最小！）
    for i in range(len(left)):
        for j in range(len(right)):
            if abs(sum(left) + right[j] - left[i] - aver) < abs(sum(left) - aver):  # 如果把右边的任一矿石和左边的交换，使得左边相对于平均重量的差的绝对值变小了，那就交换！
                left.insert(i, right.pop(j))  # 把右边组的那个元素删除并加进左边组
                right.insert(j, left.pop(i + 1))  # 同理把左边组的元素加进右边组，注意是i + 1，因为刚刚多了一个元素
    return abs(sum(left) - sum(right))  # 最后只要返回两组的差的绝对值就可以了
    pass

stone_list = [int(i) for i in input().split()]
print(solution(stone_list))

while True:
    try:
        import sys
        import random
        line = list(map(int, sys.stdin.readline().split()))
        n = len(line)
        summary = sum(line)
        m = n//2
        line = sorted(line)
        summary_1 = 0
        list_1 = []
        picked = list()
        for i in range(1000):
            j = 0
            summary_1 = 0
            picked = []
            while j <= m:
                pick = random.randint(0, n-1)
                if pick not in picked:
                    summary_1 += line[pick]
                    j += 1
                else:
                    picked.append(pick)
            summary_2 = summary - summary_1
            fa = int(abs(summary_1 - summary_2))
            list_1.append(fa)
        fama = sorted(list_1)
        print(fama[0])
    except:
        break