一、0-1背包問題的描述

下面將使用回溯法、分支界限法、動態(tài)規(guī)劃法來分析和解決此問題。

二、回溯法

（1）算法步驟

（2）代碼如下（沒有裁剪函數(shù)）：

用i和n來判斷結(jié)束與否，是因為解空間結(jié)構(gòu)是完全二叉樹，用兩節(jié)點間的邊的深度表示物品序號，用兩節(jié)點之間的邊的01值表示該物品選擇與否。

#include<stdio.h> int n, c, bestp;//物品的個數(shù)，背包的容量，最大價值 int p[10000], w[10000], x[10000], bestx[10000];//物品的價值，物品的重量，x[i]暫存物品的選中情況,物品的選中情況void Backtrack(int i, int cp, int cw) { //cw當前包內(nèi)物品重量，cp當前包內(nèi)物品價值int j;if (i>n)//回溯結(jié)束{if (cp>bestp){bestp = cp;for (i = 0; i <= n; i++)//這里從0開始也無妨，因為后面輸出是從1開始的 bestx[i] = x[i];}}elsefor (j = 0; j <= 1; j++){x[i] = j;if (cw + x[i] * w[i] <= c){cw += w[i] * x[i];cp += p[i] * x[i];Backtrack(i + 1, cp, cw);cw -= w[i] * x[i];cp -= p[i] * x[i];}} }int main() {int i;bestp = 0;printf("請輸入背包最大容量:\n");scanf("%d", &c);printf("請輸入物品個數(shù):\n");scanf("%d", &n);printf("請依次輸入物品的重量:\n");for (i = 1; i <= n; i++)scanf("%d", &w[i]);printf("請依次輸入物品的價值:\n");for (i = 1; i <= n; i++)scanf("%d", &p[i]);Backtrack(1, 0, 0);printf("最大價值為:\n");printf("%d\n", bestp);printf("被選中的物品依次是(0表示未選中，1表示選中)\n");for (i = 1; i <= n; i++)printf("%d ", bestx[i]);printf("\n");getchar(); getchar();return 0; }

2、動態(tài)規(guī)化

#include<stdlib.h> #include<stdio.h>int V[200][200];//前i個物品裝入容量為j的背包中獲得的最大價值 int max(int a, int b) //一個大小比較函數(shù)，用于當總重大于第I行時 {if (a >= b)return a;else return b; }void Knap(int n, int w[], int v[], int x[], int C) {int i, j;for (i = 0; i <= n; i++)V[i][0] = 0;for (j = 0; j <= C; j++)//j居然是離散的V[0][j] = 0;for (i = 0; i <= n - 1; i++)for (j = 0; j <= C; j++)if (j<w[i])V[i][j] = V[i - 1][j];elseV[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);//輸出相應的選擇物品j = C;for (i = n - 1; i >= 0; i--){if (V[i][j]>V[i - 1][j]){x[i] = 1;j = j - w[i];}elsex[i] = 0;}printf("選中的物品是:\n");for (i = 0; i<n; i++)printf("%d ", x[i]);printf("\n");}int main() {int s;//獲得的最大價值int w[4];//物品的重量 重量 價值 和物品的狀態(tài) 均對應著存到數(shù)組中，物品從1開始。 int v[4];//物品的價值int x[4];//物品的選取狀態(tài) 選中則是1 沒選中為0 int n, i;int C;//背包最大容量n = 4;printf("請輸入背包的最大容量:\n");scanf("%d", &C);printf("物品數(shù):\n");scanf("%d", &n);printf("請分別輸入物品的重量:\n");for (i = 0; i<n; i++)scanf("%d", &w[i]);printf("請分別輸入物品的價值:\n");for (i = 0; i<n; i++)scanf("%d", &v[i]);Knap(n, w, v, x, C);printf("最大物品價值為:\n");printf("%d\n", s);system("pause");return 0; }

總結(jié)

以上是生活随笔為你收集整理的从0-1背包问题学习回溯法、分支界限法、动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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