165. 小猫爬山(状压dp)

悠悠 2021-11-10 09:24 302阅读 0赞

翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>\_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN

。

当然，每辆缆车上的小猫的重量之和不能超过W。

每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？  
输入格式

第1行：包含两个用空格隔开的整数，N和W。

第2…N+1行：每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci

。  
输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。  
数据范围

1≤N≤18  
,  
1≤Ci≤W≤108

输入样例：

5 1996  
1  
2  
1994  
12  
29

输出样例：

分析：  
这个题可以用dfs+ 剪枝可以过。  
还可以用状压dp。  
dp\[i\]\[j\] 表示第i辆车 在j这个形式下所放的体积大小。  
j这个形式并不是指第i辆车的形式，而是指前i辆车的形式。  
注意二进制&运算的优先级。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    #define INF 1001000010
    
    int n,W;
    int c[20];
    int dp[20][1 << 19];
    
    int main()
    {
        scanf("%d%d",&n,&W);
        for(int i = 0; i < 20; i ++)
            for(int j = 0; j < (1 << 19); j ++)
                dp[i][j] = INF;
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d",&c[i]);
            dp[i][1 << (i - 1)] = c[i];
        }
        dp[1][0] = 0;
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 0; j < (1 << (n)); j ++)
            {
                if(dp[i][j] == INF)
                    continue;
                for(int k = 1; k <= n; k ++)
                    if(((j&(1<<(k - 1)))== 0) && dp[i][j] + c[k] <= W)
                        dp[i][j|(1<<(k-1))] = min(dp[i][j|(1<<(k-1))],dp[i][j] + c[k]);
                    else
                        dp[i + 1][j|(1<<(k-1))] = min( dp[i + 1][j|(1<<(k-1))],c[k]);
            }
            if(dp[i][(1 << (n)) - 1] != INF)
            {
                printf("%d\n",i);
                return 0;
            }
        }
    }