3.4 零食

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

小八同学最近爱上了吃零食，但是他又想追求健康的生活。每一包零食都有一个能量值，小八同学每次都一定要吃总能量刚好为\(v\)的零食才肯罢休。而且小八同学又很懒，他希望通过吃数量最少的零食达到这个目的。所以他希望你能设计一个程序帮他决定要吃哪些零食。

给定每种零食所包含的能量和数目，你的任务是给出所要吃的零食的最小数目。

数据输入

先输入一行包含 2 个整数\(v\ (v\leq 20000)\)、\(n\)，表示小八需要吃能量值和为\(v\)的零食，而零食一共有\(n\)种，下面输入\(n\)行，每行 2 个整数，第一个表示该种零食的能量值（能量值大于 0），第二个表示该种零食的总数。所有零食的总数量不会超过 50。

数据输出

输出一行包含一个整数表示小八最少需要吃的零食数量，若小八无法通过吃零食达到\(v\)的能量值，则输出“Fail”。

输入示例 输出示例
10 2
4 1
2 10		 4
10 2
4 1
7 3		 Fail

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <string.h>
#define maxn 51
#define maxm 20005
#define fminmax min
inline int min(int x, int y) { return x < y ? x : y; }
int V[maxn], C[maxn], dp[maxm];//, W[maxn] (if necessary)

//多重背包O(V\times \sum log C_i)
int main() {
    int v, n, i, j, k, tempv;
    scanf("%d%d", &v, &n);
    for (i = 0; i < n; ++i)
        scanf("%d%d", V + i, C + i);
    memset(dp, 0x7f, sizeof(dp));
    dp[0] = 0;
    for (i = 0; i < n; ++i) {
        if (C[i] == 1) {//01背包问题，虽然这题没必要，但是为了举一反三！
            for (j = v; j >= V[i]; --j)
                dp[j] = fminmax(dp[j], dp[j - V[i]] + 1);//1->W[i]
        }
        else if (V[i] * C[i] >= v) {//转化为完全背包问题
            for (j = V[i]; j <= v; ++j)
                dp[j] = fminmax(dp[j], dp[j - V[i]] + 1);//1->W[i]
        }
        else {
            k = 1;//多重背包问题
            while (k < C[i]) {
                tempv = k * V[i];
                for (j = v; j >= tempv; --j)
                    dp[j] = fminmax(dp[j], dp[j - tempv] + k);//k->k*W[i]
                C[i] -= k;
                k <<= 1;
            }
            tempv = C[i] * V[i];
            for (j = v; j >= tempv; --j)
                dp[j] = fminmax(dp[j], dp[j - tempv] + C[i]);//C[i]->C[i]*W[i]
        }
    }
    if (dp[v] < 0x7f7f7f7f)
        printf("%d\n", dp[v]);
    else
        printf("Fail\n");
    return 0;
}

设计思路与复杂度分析

此题为多重背包问题，具体请参考背包九讲第1-3讲。做法是将第\(i\)种物品分成了\(log C_i\)种物品，将原问题转化为复杂度为\(O(V\times \sum log C_i)\)的 01 背包问题。

本题实现的时候已经将01背包、多重背包、完全背包均包括了。如果遇到类似题目可以直接从中举一反三。

附多重背包问题通用描述：有\(N\)种物品和一个容量为\(V\)（本题为总能量\(m\)）的背包。第\(i\)种物品最多有\(C_i\)件可用，每件耗费的空间是\(V_i\)，价值是\(W_i\)（本题价值为1，即占用1 个数量）。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过（刚好等于）背包容量，且价值总和最大（最小）。

关于0x7f的说明：由于\(memset\)函数是来自\(string.h\)库的函数，所以其操作对象为字节，将\(int\)数组按字节初始化为0x7f，实际得到的是0x7f7f7f7f。已经几乎达到了\(int\)的极限。不存在两个极大值相加的情况可以这样初始化，如果存在两个极大值相加的情况可以初始化为0x3f，其为0x7f的一半。

0%