[USACO12MAR]摩天大楼里的奶牛

标签： 动态规划 状态压缩

---

题目描述

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don’t like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.

题目翻译：给出n个物品，体积为w[i]，现把其分成若干组，要求每组总体积<=W，问最小分组。(n<=18)

输入输出格式

输入格式

• Line 1: N and W separated by a space.

• Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.

输出格式

• A single integer, R, indicating the minimum number of elevator rides needed.
  one of the R trips down the elevator.

输入输出样例

输入样例#1：

4 10
5
6
3
7

输出样例#1：
3

题解

遇到有关背包容量的问题，我们可以把方程设计为在某个状态下剩余容量最大，则答案最后只需判定一下即可。
设f[i][j]表示放入物品状态为i时需要j个背包，当前背包的剩余最大体积。
那么对于每一个物品，看它的体积是否超过当前最大体积，如果没有则装入，否则新开一个背包装入。

#include<bits/stdc++.h>
#define N 20
#define M (1 << 18)
using namespace std;

int n, w, ans;
int a[N], f[M][N];

int main()
{
    memset(f, -1, sizeof(f));
    scanf("%d%d", &n, &w);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        f[1 << (i - 1)][1] = w - a[i];
    }
    for(int j = 1; j <= n; j ++)
        for(int i = 1; i < (1 << n); i ++)
            for(int k = 1; k <= n; k ++)
                if(!(i & (1 << (k - 1))) && f[i][j] != -1)
                   if(f[i][j] >= a[k]) 
                      f[i | (1 << (k - 1))][j] = max(f[i | (1 << (k - 1))][j], f[i][j] - a[k]);
                    else f[i | (1 << (k - 1))][j + 1] = max(f[i | (1 << (k - 1))][j + 1], w - a[k]);
    for(int j = n; j >= 1; j --)
        if(f[(1 << n) - 1][j] != -1) 
           ans = j;
    printf("%d", ans);
    return 0;
}