小猫爬山

小猫爬山 (dp \(\circ\))

• \(Freda\) 和 \(rainbow\) 饲养了 \(N\) 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
• \(Freda\) 和 \(rainbow\) 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 \(W\)，而 \(N\) 只小猫的重量分别是\(C_1,C_2,…,C_N\)。当然，每辆缆车上的小猫的重量之和不能超过 \(W\)。每租用一辆缆车，\(Freda\) 和 \(rainbow\) 就要付 \(1\) 美元，所以他们想知道，最少需要付多少美元才能把这 \(N\) 只小猫都运送下山？

Input

• 第一行包含两个用空格隔开的整数，\(N\) 和 \(W\)。
• 接下来 \(N\) 行每行一个整数，其中第 \(i+1\) 行的整数表示第 \(i\) 只小猫的重量 \(C_i\)。

Output

• 输出一个整数，最少需要多美元也就是辆缆车。

Sample Input

5 1996
1
2
1994
12
29 

Sample Output

2

Hint

• 对于\(100\%\) 的数据，\(1<=N<=18,1<=C_i<=W<=10^8\)。

分析

• 方法一：暴力\(dfs\)
• 方法二：暴力状压裸搜。

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,W,w[20],f[1<<18],i,j,ans,Max;
void Min(int &a,int b){if(a>b)a=b;}
void Solve(){
    scanf("%d%d",&n,&W);
    int Max=1<<n;//最大状态
    for(i=0;i<n;i++)
        scanf("%d",&w[i]);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(ans=1;;ans++){//枚举索道
        for(i=0;i<Max;i++)
            if(f[i]<=W)f[i]=0;//前ans-1个缆车能运走的状态清零
        for(i=0;i<Max;i++)
            if(f[i]<W)//表示i状态下还可以放,f[i]=0,则表示另开新缆车
                for(j=0;j<n;j++)//枚举猫
                    if(!(i>>j&1))Min(f[i|(1<<j)],f[i]+w[j]);
        if(f[Max-1]<=W){printf("%d\n",ans);break;}
    }
}
int main(){
    Solve();
    return 0;
}