6.2 水果沙拉

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

实验任务

小\(X\)同学最近胖了许多，准备减肥。他决定每天用水果沙拉代替三餐来节食减肥。他从超市买了\(n\)种水果，每种水果有对应的美味度\(a_i\)和所含的卡路里\(b_i\)，他将从中选择一些水果来做水果沙拉，但根据减肥的原则，水果美味度的和要严格等于水果卡路里和的\(K\)倍。为了让自己能持续减肥，小\(X\)同学希望水果沙拉尽量好吃，即美味度尽量大，你能帮他吗？

数据输入

输入的第一行为包括两个整数\(n,k\ (1\leq n\leq 100,\ 1\leq k\leq 10)\)表示水果种类数和减肥原则中的\(k\)值。接下来一行，\(n\)个整数\(a_i\ (1\leq a_i\leq 100)\)表示\(n\)种水果的美味度。最后一行，\(n\)个整数\(b_i\ (1\leq b_i\leq 100)\)表示\(n\)种水果的卡路里。

数据输出

输出满足减肥原则的前提下小\(X\)同学能获得的最大美味度，若无法满足原则，则输出\(-1\)。

输入示例 输出示例
3 2
10 8 1
2 7 1		 18
5 3
4 4 4 4 4
2 2 2 2 2		 -1

源代码（动态规划）

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
#include <stdio.h>
#include <string.h>

#define NInf 0xfefefefe
#define MAX_N 105
#define MAX_A 105
#define MAX_V 2 * MAX_N * MAX_A

int dp[MAX_V];
int w_a[MAX_N];
int v_b[MAX_N];

inline int max(int a, int b){ return a < b ? b : a; }

int main(){
    int i, j, n, k, v;
    scanf("%d %d", &n, &k);
    int offset = n * MAX_A;
    v = 2 * offset;
    for (i = 0; i < n; ++i){
        scanf("%d", &w_a[i]);
    }
    for (i = 0; i < n; ++i){
        scanf("%d", &v_b[i]);
        v_b[i] = w_a[i] - k*v_b[i];
    }
    memset(dp, NInf, sizeof(dp));
    dp[offset] = 0;
    for (i = 0; i < n; ++i){
        if (v_b[i] > 0){//依赖下标更小的，所以由大至小dp
            for (j = v - 1; j >= v_b[i]; --j){
                dp[j] = max(dp[j], dp[j - v_b[i]] + w_a[i]);
            }
        }
        else{//依赖下标更大的，所以由小至大dp
            for (j = 0; j < v + v_b[i]; ++j){//@$v_i<0$@
                dp[j] = max(dp[j], dp[j - v_b[i]] + w_a[i]);
            }
        }
    }
    printf("%d\n", dp[offset] == 0 ? -1 : dp[offset]);
    return 0;
}

设计思路与复杂度分析

此题类似0-1背包问题，但是加入了约束条件：\(\sum a = k\times\sum b\)。自然首先考虑如何转化为背包问题，现将约束条件转化为：\(\sum a - k \times \sum b = 0\)。则得到背包问题如下： \[ \left\{ \begin{array}{l} v_i = a_i - k\times b_i \\ w_i = a_i \\ \end{array} \right. \] 其状态转移方程为：\(dp(i,j)=max(dp(i-1,j),dp(i-1,j-v_i)+w_i)\)。这是一个物品体积为\(v_i\)，而价值为\(w_i\)的0-1背包问题。与标准0-1背包问题的不同之处在于体积可能为负，所以需要加一个offset。而且最后要求\(v=0\)，所以输出的是\(dp(n,offset)\)。

可将offset设置为\(maxa\times n\)，证明如下。当a极大，b极小时，得到下标的上界为\(maxa \times n\)。当a极小，b极大时得到下标的下界为\(-k\times maxb\times n\)。那么简单的将offset设置为\(-k\times maxb\times n\) 也是可以的，但是内存负担和计算负担均很大。其实如果一旦有前面选取的物品体积和小于\(-maxa\times n\)，那么后面即使所有\(a\)加起来也不可能改变总体积为负的局面，所以\(dp\) 数组\(-maxb\times n \sim -maxa\times n\)段无实际意义，可以省略。即offset设置为\(maxa\times n\)。

由于\(v_i\)符号不确定，所以将公式中二维数组优化为一维数组的时候需要额外考虑处理方向问题，详见备注。

0%