题目描述

Freda 和 rainbow 饲养了 N 只小猫, 这天, 小猫们要去爬山. 经历了千辛万苦, 小猫们终于爬上了山顶, 但是疲倦的它们再也不想徒步走下山了 (呜咕).

Freda 和 rainbow 只好花钱让它们坐索道下山. 索道上的缆车最大承重量为 W, 而 N 只小猫的重量分别是 C1、C2……CN. 当然, 每辆缆车上的小猫的重量之和不能超过 W. 每租用一辆缆车, Freda 和 rainbow 就要付 1 美元, 所以他们想知道, 最少需要付多少美元才能把这 N 只小猫都运送下山?

输入格式

第一行包含两个用空格隔开的整数, N 和 W.

接下来 N 行每行一个整数, 其中第 i+1 行的整数表示第 i 只小猫的重量\(C_i\).

输出格式

输出一个整数, 最少需要多少美元, 也就是最少需要多少辆缆车.

样例输入

5 1996
1
2
1994
12
29

样例输出

2

数据范围与约定

对于 100% 的数据,\(1 \leq N \leq 18, 1 \leq C_i \leq W \leq 10^8\).

Explanation

用了 IDA*之后便觉得这道题有点玄学的范畴了~ 目测之后还得好好研究一下剪枝搜索.

直接引用官方题解:

从 1~ N 枚举答案, 限制当前搜索深度为枚举的数 (迭代加深).

每次 dfs 时, 枚举每只小猫被放在了哪一个缆车上.

剪枝: 第 i 只小猫只能放在前 i 个缆车上 (放到更后面的车上没有意义).

这样极限复杂度是\(O(N!)\), 但是缆车还有容量限制, 加上我们采用迭代加深, 一旦找到答案

可以立即退出, 这样就已经能通过此题了.

Example Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 20;
bool larger(int a, int b) { return a > b; }

int n, m, arr[maxn];
int IDL = 0; // Iteration depth limit
int cap[maxn]; // Capacity of each cable car

// Deep first search with IDA* optimization
bool dfs(int p)
{
    if (p > n)
        return true;
    // For each cable car...
    for (int i = 1; i <= p && i <= IDL; i++)
        if (cap[i] + arr[p] <= m) {
            // Test if this can be inserted
            cap[i] += arr[p];
            if (dfs(p + 1))
                return true;
            // Failure, retry another after reset
            cap[i] -= arr[p];
        }
    return false;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    sort(arr + 1, arr + 1 + n, larger);
    for (IDL = 1; IDL <= n; IDL++) {
        memset(cap, 0, sizeof(cap));
        if (dfs(1))
            break;
    }
    printf("%d\n", IDL);
    return 0;
}