完全背包。

背包相关问题具体参见背包九讲。
这里用一种朴素的转化为01背包的方法,就是把每一个物品看成 $ [0,\lfloor \frac{V}{w[i]} \rfloor] $ 个。

$$ dp[x][i] = \begin{cases} \min(dp[x][i-w[x]], dp[x-1][i]) + P[i], & w[x] \le i \\\\ dp[x-1][i], & w[x] > i \\\\ \end{cases} $$

容易发现 $ x $ 一维可以滚掉。
一种更加高效的方法是拆成2的幂次方个,这能组成所有的情况是个 trivial conclusion 。
令我惊奇的是这样反而耗时更多,想了想似乎是因为变量的读写次数会变多!?
拆成二的幂次方个也无需每次重新计算,只需记录对于特定的重量 w 的价格 p[w]。之后再通过 p[i]=min(p[i],p[i>>1]<<1)修正。具体见代码实现。

较朴素方法(1444K, 46ms)

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 10000 + 100, INF = 0x3f3f3f3f;
int dp[maxn] = {0};
int main()
{
    int t; read(t);
    while(t--)
    {
        int e, f; read(e, f);
        int size = f - e;
        int n; read(n);
        for(int i = 1; i <= size; i++) dp[i] = INF;
        dp[0] = 0;
        while(n--)
        {
            int P, W; read(P, W);
            for(int i = W; i <= size; i++)
                dp[i] = min(dp[i], dp[i - W] + P);
        }
        if(dp[size] == INF)
            puts("This is impossible.");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[size]);
    }
    return 0;
}

拆成二的幂(1484K, 967ms)

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 10000 + 100, INF = 0x3f3f3f3f;
int p[maxn] = {0}, dp[maxn] = {0};
int main()
{
    int t; read(t);
    while(t--)
    {
        int e, f; read(e, f);
        int size = f - e;
        int n; read(n);
        for(int i = 0; i <= size; i++) p[i] = dp[i] = INF;
        dp[0] = 0;
        while(n--)
        {
            int P, W; read(P, W);
            p[W] = min(p[W], P);
        }
        for(int i = 1; i <= size; i++) if(~i&1) p[i] = min(p[i], p[i >> 1] << 1);
        for(int i = 1; i <= size; i++) for(int j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + p[i - j]);
        if(dp[size] == INF)
            puts("This is impossible.");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[size]);
    }
    return 0;
}

标签: none

添加新评论