物品/容量	0	1	2	3	4	5	6	7	8	9	10	11
0/w=0	0	0	0	0	0	0	0	0	0	0	0	0
1/w=1	0	1	1	1	1	1	1	1	1	1	1	1
2/w=2	0	1	6	7	7	7	7	7	7	7	7	7
3/w=5	0	1	6	7	7	18	19	24	25	25	25	25
4/w=6	0	1	6	7	7	18	22	24	28	29	29	40
5/w=7	0	1	6	7	7	18	22	28	29	34	35	40

價(jià)值v[]={0,1,6,18,22,28}

重量w[]={0,1,2,5,6,7}

背包容量T=11

上面是求最大價(jià)值公式，不是很容易看懂

下面圖文是具體求最大價(jià)值的步驟：

c語言實(shí)現(xiàn)

動態(tài)規(guī)劃-遞歸方法

自頂向下

#include <stdio.h>//0-1背包問題#define N 6 // #define maxT 100 int c[N][maxT] = {0};int Memoized_Knapspsack(int v[N], int w[N], int T); int Calculate_Max_Value(int v[N], int w[N], int i, int j); /* T: 背包容量 v[]:價(jià)值數(shù)組 w[]:重量數(shù)組 c[][]:c[i][j]表示前i個(gè)物品在背包容量為j的情況下最優(yōu)裝包方案所能獲得的最大價(jià)值 */ int Memoized_Knapspsack(int v[N], int w[N], int T){int i,j;for (i = 0; i < N; i++){for (j = 0; j < T; j++){c[i][j] = -1;}}return Calculate_Max_Value(v, w, N-1, T);}int Map_Knapspsack(int v[N], int w[N], int T){int i,j;for (i = 0; i < N; i++){for (j = 0; j < T+1; j++){printf("%2d ", Calculate_Max_Value(v, w, i, j));}printf("\n");}}int Calculate_Max_Value(int v[N], int w[N], int i, int j){int temp = 0;if(i == 0 || j == 0){c[i][j] = 0;}else{c[i][j] = Calculate_Max_Value(v, w, i-1, j); //1.if(i > 0 && j >= w[i]){ //當(dāng)j < w[i]時(shí)c[i][j]一定是等于c[i-1][j]temp = Calculate_Max_Value(v, w, i-1, j-w[i]) + v[i]; //2.if(temp > c[i][j]){c[i][j] = temp; //3.}}}return c[i][j]; }int main(void){int v[] = {0,1,6,18,22,28};int w[] = {0,1,2,5,6,7};int T = 11;int result = Memoized_Knapspsack(v, w, T);printf("最大價(jià)值 = %d\n", result);Map_Knapspsack(v, w, T);return 0; }

結(jié)果

總結(jié)

以上是生活随笔為你收集整理的0-1背包问题-c语言实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。