Shaass and Bookshelf

题目描述

Shaass has $n$ books. He wants to make a bookshelf for all his books. He wants the bookshelf’s dimensions to be as small as possible. The thickness of the $i$-th book is $t_i$ and its pages’ width is equal to $w_i$. The thickness of each book is either $1$ or $2$. All books have the same page heights.

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.

题意概述

给定$n$个$t_i, w_i$，要求将它们分成两组，使得第一组中$t_i$之和不小于第二组中$w_i$之和。求第一组中$t_i$之和的最小值。

数据范围：$1 \le n \le 100, \ 1 \le t_i \le 2, \ 1 \le w_i \le 100$。

算法分析 1

令$f_{i, j}$表示用前$i$本书，总宽度和总长度相差$j$时总宽度的最小值。直接 DP 即可。

代码 1

#include <iostream>
using namespace std;
int n, ans, t[101], w[101], f[101][20001];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i] >> w[i];
    }
    for (int i = 0; i < 101; ++i) {
        for (int j = 0; j < 20001; ++j) {
            f[i][j] = 1e9;
        }
    }
    f[0][10000] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 20001; ++j) {
            if (f[i][j] < 1e9) {
                f[i + 1][j + t[i + 1]] = min(f[i + 1][j + t[i + 1]], f[i][j] + t[i + 1]);
                f[i + 1][j - w[i + 1]] = min(f[i + 1][j - w[i + 1]], f[i][j]);
            }
        }
    }
    ans = 1e9;
    for (int i = 10000; i < 20001; ++i) {
        ans = min(ans, f[n][i]);
    }
    cout << ans << endl;
    return 0;
}

算法分析 2

将书分成两组：一组$t_i=1$，另一组$t_i=2$。枚举从两组中分别选择$i, j$本书放在下层，计算是否合法，取最小值即可。根据贪心策略，一组中放在下层的书的$w_i$越大越好。

代码 2

#include <iostream>
#include <algorithm>
using namespace std;
struct number {
    int t, w;
} a[101];
bool cmp(number a, number b) {
    return a.t < b.t ? true : a.t == b.t ? a.w > b.w : false;
}
int n, p, ans, sum1[101], sum2[101];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].t >> a[i].w;
    }
    sort(a + 1, a + n + 1, cmp);
    p = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (a[i].t - 1) {
            p = i;
            break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        sum1[i] = sum1[i - 1] + a[i].t;
        sum2[i] = sum2[i - 1] + a[i].w;
    }
    ans = 1e9;
    for (int i = 1; i <= p; ++i) {
        for (int j = p; j <= n + 1; ++j) {
            if (sum1[i - 1] + sum1[j - 1] - sum1[p - 1] >= sum2[p - 1] - sum2[i - 1] + sum2[n] - sum2[j - 1]) {
                ans = min(ans, sum1[i - 1] + sum1[j - 1] - sum1[p - 1]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}