时间戳

首页 > 技术文章 > Timus 1005 解题报告

Timus 1005 解题报告

yinzm 2017-03-27 22:29 原文

题目链接

http://acm.timus.ru/problem.aspx?space=1&num=1005

题目大意

给你一堆石头，现在需要你将这堆石头分成两堆，要求两堆石头的重量相差最小，求这个最小的值是多少。

解题思路

看完题目之后，我们可以了解一下数据的规模，最多就20个石头，所以我们可以列出我们能够解题的一些方法：

  • 直接深度优先搜索，暴力得到每一种划分方法
  • 二进制枚举，这也是一种暴力求解方法
  • 将题目转化为01背包问题，动态规划求解

结合题目时间限制，我们最终选择第三种方法。所以现在来重点讲解下，这个题目需要怎么转化为01背包问题的。
首先，将石头划分成AB两堆，那么我们相当于从一堆石头里面挑选出若干个石头出来。对于每一块石头都有挑选或者不挑选两种选择。这就有点像01背包问题了，但是目前还不确定如何用01背包来求解。题目要求我们求解两堆石头的最小差，如果石头是可以掰开的，那么最理想的状态当然是两堆石头的重量都是原始那堆石头重量的一半avg，但是现实不是那么完美的，我们不能将石头掰开揉碎，而且很有可能最终的最好结果确实是一堆重一堆轻。
假设最优的结果是一堆石头重量为A，另外一堆是B，那么AB两者可能是其中一个大于等于avg，另外一个是小于等于avg。我们现在需要使|A-B|最小，那么最好是AB越靠近avg越好，这就相当于我们拿一个最大承重为avg的袋子去装石头，最多能装多少重量的石头。这就是一个01背包问题了。接下来我们只要求出这个背包问题的解，那么最后的差也就能够计算出来了。

解题代码

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int wights[25];
int dp[25][100000*10+10];

int pack01(int volume) {
    for (int i = 0; i <= volume; ++i) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int v = 0; v <= volume; ++v) {
            if (v >= wights[i-1]) {
                dp[i][v] = max(dp[i-1][v], dp[i-1][v-wights[i-1]]+wights[i-1]);
            } else {
                dp[i][v] = dp[i-1][v];
            }
        }
    }
    return dp[n][volume];
}

int main() {
    while (~scanf("%d", &n)) {
        int tot = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &wights[i]);
            tot += wights[i];
        }
        int ans = pack01(tot/2);
        printf("%d\n", tot-2*ans);
    }
    return 0;
}

但是这种写法是有问题的，会超内存。所以我们应该用滚动数组来进行空间优化。

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int wights[25];
int dp[100000*10+10];

int pack01(int volume) {
    for (int i = 0; i <= volume; ++i) {
        dp[i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int v = volume; v >= 0; --v) {
            if (v >= wights[i-1]) {
                dp[v] = max(dp[v], dp[v-wights[i-1]]+wights[i-1]);
            }
        }
    }
    return dp[volume];
}

int main() {
    while (~scanf("%d", &n)) {
        int tot = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &wights[i]);
            tot += wights[i];
        }
        int ans = pack01(tot/2);
        printf("%d\n", tot-2*ans);
    }
    return 0;
}

我之所以解这个题目是因为，网易今年笔试出了一个这样的题目：
一种双核CPU的两个核能够同时处理任务，现在有n个一直数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb数据，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案处理完这批任务所需要的时间最少，求这个最小的时间。

数据规模：
任务数最多为50个，每个任务的大小都是1024kb的整数倍，最大为4194304kb.

对于这样一种规模的数据，我们就绝对不能再暴力求解了。动态规划是一个很好的选择，但是在实际操作的过程中，我们需要注意空间的问题，因为每个任务都是1024kb的整数倍，所以我们可以将数据放缩到1到4096，这样再去解题才能通过。

推荐阅读