今天繼續背包問題相關解法，主要內容：動態規劃
想到這個解法是想到了前幾天的一道軟考軟體設計師考試的下午演算法考題，我是參加者，內容大概如下：通常每種食物往往有不同的營養價值，顧客往往需要一種演算法實現用最少的花費獲得最高的營養價值，（食物不重複），現在要求在花費 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;
}