I - Coins dp

http://acm.hdu.edu.cn/showproblem.php?pid=2844

这个题目是一个多重背包转化成01背包

题意: Whuacmers拥有bi个面值为ai的硬币，现在他要用这些硬币买价格不超过m的一个物品，问你最多能刚好能用硬币付钱的物品价格有几个(即该价格能用这些硬币凑出来)。

思路: 看到多重背包问题,第一时间想到的是转化为01背包来做,即我们把这个物品能选取多次当成有多个相同的物品给我们选取，复杂度是o(m*(bi的和))，根据题目给出的数据范围，这个方法的复杂度是妥妥的TLE的，我们需要对这个方法进行优化，我们可以用二进制的思想来考虑.

将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1,2,22…2k−1,bi−2k+1，且k是满足bi−2k+1 > 0的最大整数。例如，如果bi为13，则相应的k = 3，这种最多取13件的物品应被分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为bi，表明不可能取多于bi件的第i种物品。另外这种方法也能保证对于0…bi间的每一个整数，均可以用若干个系数的和表示。

下面是一个模板，我觉得写的特别好

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

#define inf64 0x3f3f3f3f3f3f3f3f

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e6 + ;

int num[maxn], dp[maxn], val[maxn];

int N,V;

void zero(int weight,int value)

{

    for(int i=V;i>=weight;i--)

    {

        dp[i] = max(dp[i], dp[i - weight] + value);

    }

}

void all(int weight,int value)

{

    for(int i=weight;i<=V;i++)

    {

        dp[i] = max(dp[i], dp[i - weight] + value);

    }

}

void solve()

{

    int t = ;

    int ncount = ;

    for(int i=;i<=N;i++)

    {

        if (num[i] * val[i] >= V) all(val[i], val[i]);

        else

        {

            t = ;

            ncount = num[i];

            while(t<=ncount)

            {

                zero(t*val[i], t*val[i]);

                ncount -= t;

                t *= ;

            }

            zero(ncount*val[i], ncount*val[i]);

        }

    }

}

int main()

{

    while(cin>>N>>V&&N!=&&V!=)

    {

        for (int i = ; i <= N; i++) scanf("%d", &val[i]);

        for (int i = ; i <= N; i++) scanf("%d", &num[i]);

        memset(dp, -inf, sizeof(dp));

        dp[] = ;

        solve();

        int ans = ;

        for(int i=;i<=V;i++)

        {

            if (dp[i] > ) ans++;

            //printf("dp[%d]=%d\n",i, dp[i]);

        }

        printf("%d\n", ans);

    }

    return ;

}

巴特西

I - Coins dp

最新文章

热门文章