学步园

问题描述： 有一个饮料公司，供应 t_max 种饮料， 最大供应容量为 v_max, 每种饮料由如下属性组成 T { C, V, H }, 其中C,V,H分别代表每种饮料的最大供应数量(瓶数)，每瓶的容量，没瓶的客户满意度。

问题： 给出饮料序列，求满意度最高的饮料组合(每种饮料各需要多少瓶，以及满意度的最大值)

最优化问题一般可以用动态规划或者贪心算法解决，此处容易将问题化为递推式

用 f(v, t) 表示供应容量为 v 时， 第 t ~ t_max - 1 种饮料的最优满意度(饮料编号从0～t_max-1)。k表示第t中饮料需要k瓶，有如下式子

f(v, t) = k * H[t] + f(v - k * V[t], t + 1)

其中限制条件有

1） k <= C[t]， 瓶数最大值条件

2） k * V[t] <= v， 中断瓶数循环条件

3) t + 1 < t_max， 递归结束条件

程序如下

#include<stdio.h>

#define V_MAX 100   // 饮料公司提供的饮料最大容量
#define T_MAX 3 // 饮料种类总数

int V[T_MAX] = {5, 10, 15};  // 每种饮料每瓶的容量
int C[T_MAX] = {5, 10, 2};  // 每种饮料最多可提供的瓶数
int H[T_MAX] = {5, 9, 20};    // 每种饮料每瓶的满意度
int OPT_C[V_MAX][T_MAX];   
// OPT_C[v][t] = c 代表剩余可提供饮料容量为v时
// 第t种饮料的最优数量是c
// 此数组充当备忘录数组，也记录最优解的各饮料瓶数

/**
* 初始化二维数组
**/
void init_2darray(int arr[V_MAX][T_MAX], int val) {
    for (int i = 0; i < V_MAX; i++)
        for (int j = 0; j < T_MAX; j++)
            arr[i][j] = val;
}

/**
* 求最优解函数
* opt(v, t)表示可提供容量为v时，t～T_MAX-1种饮料的最优满意度
**/
int opt(int v, int t) {
    if (t >= T_MAX) return 0;

    int copt = 0;
　　 // j代表所选的饮料瓶数 
    for (int j = 0; j <= C[t]; j++) {
        int ch = j * H[t];
        int cv = j * V[t];
        if (cv > v) break;  // 所选瓶数总容量超过可提供容量
        if ((t + 1 < T_MAX) && (OPT_C[v - cv][t + 1] != -1)) {
            // 如果可提供容量为v-cv时的第t+1种饮料的最优解已经计算过
            ch += (OPT_C[v - cv][t + 1] * H[t + 1]);
        } else {
            ch += opt(v - cv, t + 1); // 计算如果第t种饮料选j瓶的最优满意度
        }
        if (ch > copt) {
            copt = ch;
            OPT_C[v][t] = j;    // 记录可提供容量为v时第t种饮料的最优瓶数
        }
    }

    return copt;
}

/**
* 输出最优解详细信息
**/
void print_opt(int t) {
    int v_left = V_MAX;
    printf("type      unit_vol  unit_sat  num       vol       sat\n");
    for (int i = 0; i < t; i++) {
        int opt_t = OPT_C[v_left][i];
        printf("%-10d%-10d%-10d%-10d%-10d%-10d\n", i, V[i], H[i], opt_t, opt_t * V[i], opt_t * H[i]);
        v_left -= (OPT_C[v_left][i] * V[i]);
    }
    printf("\n");
}

int main(void) {
    init_2darray(OPT_C -1);
    int r = opt(V_MAX, 0);
    print_opt(T_MAX);
    printf("V_MAX: %d\tT_MAX: %d\ttotal_sat: %d\n", V_MAX, T_MAX, r);
    return 0;
}

 

 程序的关键是OPT_C数组以及f(v, t)函数

OPT_C[v][t]数组的作用有两个：

1） 记录可提供容量为v时，t~t_max-1种饮料要取得最优满意度的第t种饮料的瓶数,用于最后输出最优解的饮料结果

2) 充当备忘录，当计算 f(v, t)时，如果OPT_C[v][t] 已经有值，可以直接获取这个瓶数，避免重复递归计算

——————————————————————————————————————————————

<编程之美>上提供了此问题的贪心算法思路，这个问题不能简单的用单位容量满意度最高的饮料最大瓶数来贪心计算，因为有最大限制容量和单位饮料容量，所以用贪心也许可以，但可能要考虑更多。有兴趣的朋友可以研究一下