Codeforce 370J Bottles(动态规划-01背包）

题目链接：http://codeforces.com/problemset/problem/730/J

题目大意：有n个杯子， 每个杯子有两个值一个是已装水量，一个是可装水量。从一个杯子向另一个杯子倒1单位体积的水，时间花费为1s。 现在用n个杯子中的s个来装所有水， 求最小的s， 以及最少花费的时间。

解题思路：有了n杯水的总水量， 可以按照n个杯子的大小排序， 然后就可以求出最小的s。然后就可以将题目看做是求从n个杯子里面选s个，这s个杯子的总的可装水量是大于等于总水量，这种情况下这n个杯子实际装水量的最大值。因为，这s个杯子是可以装下所有水的， 那么花费时间不就其他n-s个杯子里面的总水量， 那么这n-s个杯子的总水量越小那么花费时间越少， 那么就是这s个杯子水量越大。

定义：dp[i][j][k]代表第i个杯子，可装水量为j时， 已选k个杯子的最大实际装水量。

那么递推方程应为dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][i-a[x]][k-1] + b[x]),然后可以优化成二维的，即可求解：

代码如下：

#include<bits/stdc++.h>
using namespace std;

pair<int, int> par[107];
int dp[10007][107];

bool cmp(const int &a, const int &b)
{
    return a > b;
}

pair<int, int> cou(int n)
{
    int res[107], f = 0;
    for(int i=1; i<=n; ++ i)
        f += par[i].first, res[i] = par[i].second;
    sort(res + 1, res + n + 1, cmp);
    int s = 0;
    for(int i=1; i<=n; ++ i)
    {
        s += res[i];
        if(s >= f)
            return make_pair(s, i);
    }
}

int main()
{
    int n;
    scanf("%d", &n);

    int s = 0;
    for(int i=1; i<=n; ++ i)
    {
        scanf("%d", &par[i].first);
        s += par[i].first;
    }
    for(int i=1; i<=n; ++ i)
        scanf("%d", &par[i].second);

    pair<int, int> t = cou(n);
    for(int i=1; i<=t.first; ++ i)
    {
        for(int k=0; k<= t.second; ++ k)
        {
            dp[i][k] = -100000000;
        }
    }
    dp[0][0] = 0;
    for(int i=1; i<=n; ++ i)
    {
        for(int j=t.first; j>=par[i].second; -- j)
        {
            for(int k=1; k<=t.second; ++ k)
            {
                dp[j][k] = max(dp[j][k], dp[j-par[i].second][k-1] + par[i].first);
            }
        }
    } 
    int mx = 0;
    for(int i=s; i<=t.first; ++ i)
    {
        if(dp[i][t.second] > mx)
            mx = dp[i][t.second];
    }
    printf("%d %d
", t.second, s - mx);
}