[算法]背包问题的动态规划算法解答，C语言实现
今天继续背包问题相关解法，主要内容：动态规划
想到这个解法是想到了前几天的一道软考软件设计师考试的下午算法考题，我是参加者，内容大概如下：通常每种食物往往有不同的营养价值，顾客往往需要一种算法实现用最少的花费获得最高的营养价值，（食物不重复），现在要求在花费N元钱获得最大营养价值
分析：相信求解的原理不用说了，背包问题，软考的题录使用的是动规算法，跟今天的主题相关，那我们看下面的代码吧。
本题动规解法的原理：由于客户选择不同的食物会产生不同的营养结果，因此我们需要动态绑定两者之间的价格和营养价值总和和关系，建立一个关联数组，这样的话每一种价格花费会产生不同结果，我们再进行大小筛选，就是在已有的选择的前提下再增加一定价格的食物，如果相加之后超出则排除，或者相加它的营养价值之后小于相加一种更价格便宜的食物的话也排除，这样可以求出每一个价位的食品的最大营养价值，然后根据要求输出某一价位的结果
关于下面的解数组，因为我们得到的结果是某一价位的最大营养价值，需要依次求出是哪些食物在这个清单里面，所以在f[i][S] == f[i+1][S]之间进行比较，相同表示营养价值不变，不添加，否则表示添加了食物i，输出结果
/* *背包问题之动态规划解法结合营养套餐问题 *author cg *date 2008 12 26 / #include "stdio.h" #define N 6 /*定义食物数量*/ #define S 100 /*最大营养大小*/ int main() { int p[N] = {100,22,80,25,10};/*测试数据表示价格*/ int w[N] = {50,30,51,12,5};/*测试数据表示营养*/ int f[ N + 1 ][ N + 1];/*动态价格营养关系数组*/ int result = 0;/*要求的结果*/ int x[ N ] = {0};/*定义解数组*/ int i,j;/*定义计数器*/ int temp; for (j = 0; j < S+1; j++) f[N][j] = 0;/*初始化*/ for (j = w[N]; j <= S; j++) f[N][j] = p[N];/*初始化价格*/ for(i = N-1; i > 1; i--) { for(j = 0; j < S+1; j++) f[i][j] = f[i+1][j]; for(j = w[i]; j <= S; j++){ f[i][j] = f[i+1][j] > f[i+1][j-w[i]] + p[i] ? f[i+1][j] : f[i+1][j-w[i]] + p[i];/*判断是否是最大的值,否则保持*/ }/*for*/ }/*for*/ f[1][S] = f[2][S]; if (S >= w[1]) f[1][S] = f[1][S] > f[2][S-w[1]] + p[1] ? f[1][S] : f[2][S-w[1]] + p[1];/*处理最终结果*/ temp= f[1][S]; for (i = 1; i < N; i++){/*解数组*/ if (f[i][S] == f[i+1][S]) x[i] = 0; else { x[i] = 1; temp-= w[i];/*减去已经添加的营养*/ }/*else*/ }/*for*/ x[N] = f[N][S] ? 1 : 0; result = f[1][S]; printf("best is %dn", result);/*输出最大的结果*/ for (i = 1; i <= N ; i++) {/*逐个输出结果*/ if (x[i] == 1) { printf(" the p: %d", p[i]); printf(" the w: %dn", w[i]); }/*if*/ }/*for*/ system("pause"); return 0; } |
Recent Comments