背包問題是計算機科學中的經典問題之一，廣泛應用于資源分配、投資決策等領域。動態規劃是解決背包問題的有效方法之一，能夠高效地求解各種背包問題。本文將詳細介紹如何使用C語言通過動態規劃解決0-1背包問題、完全背包問題和多重背包問題，并提供相應的代碼實現。
動態規劃（Dynamic Programming, DP）是一種分階段解決問題的方法，通過將問題分解為若干個子問題，逐步求解并保存中間結果，從而避免重復計算，提高效率。
0-1背包問題是最基本的背包問題，每種物品只有一件，可以選擇放入或不放入背包。
完全背包問題中，每種物品有無限件，可以選擇放入多件。
多重背包問題中，每種物品有有限件，可以選擇放入多件，但數量有限。
給定N件物品和一個容量為V的背包，每件物品有一個重量w[i]和一個價值v[i]，求解如何選擇物品放入背包，使得背包中的總價值最大。
定義dp[i][j]表示前i件物品放入容量為j的背包中所能獲得的最大價值。
對于第i件物品，有兩種選擇： - 不放入背包：dp[i][j] = dp[i-1][j] - 放入背包：dp[i][j] = dp[i-1][j-w[i]] + v[i]
因此，狀態轉移方程為：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
#define MAX_V 1000
int max(int a, int b) {
return a > b ? a : b;
}
int knapsack(int N, int V, int w[], int v[]) {
int dp[MAX_N + 1][MAX_V + 1] = {0};
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j >= w[i - 1]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][V];
}
int main() {
int N = 5;
int V = 10;
int w[] = {2, 2, 6, 5, 4};
int v[] = {6, 3, 5, 4, 6};
int result = knapsack(N, V, w, v);
printf("Maximum value: %d\n", result);
return 0;
}
給定N件物品和一個容量為V的背包，每件物品有一個重量w[i]和一個價值v[i]，且每種物品有無限件，求解如何選擇物品放入背包，使得背包中的總價值最大。
定義dp[i][j]表示前i件物品放入容量為j的背包中所能獲得的最大價值。
對于第i件物品，可以選擇放入0件、1件、2件……直到背包容量不足。因此，狀態轉移方程為：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
#define MAX_V 1000
int max(int a, int b) {
return a > b ? a : b;
}
int complete_knapsack(int N, int V, int w[], int v[]) {
int dp[MAX_N + 1][MAX_V + 1] = {0};
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j >= w[i - 1]) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i - 1]] + v[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][V];
}
int main() {
int N = 5;
int V = 10;
int w[] = {2, 2, 6, 5, 4};
int v[] = {6, 3, 5, 4, 6};
int result = complete_knapsack(N, V, w, v);
printf("Maximum value: %d\n", result);
return 0;
}
給定N件物品和一個容量為V的背包，每件物品有一個重量w[i]、一個價值v[i]和一個數量n[i]，求解如何選擇物品放入背包，使得背包中的總價值最大。
定義dp[i][j]表示前i件物品放入容量為j的背包中所能獲得的最大價值。
對于第i件物品，可以選擇放入0件、1件、2件……直到數量n[i]或背包容量不足。因此，狀態轉移方程為：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*w[i]] + k*v[i]) for k in [0, n[i]]
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
#define MAX_V 1000
int max(int a, int b) {
return a > b ? a : b;
}
int multiple_knapsack(int N, int V, int w[], int v[], int n[]) {
int dp[MAX_N + 1][MAX_V + 1] = {0};
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= n[i - 1] && k * w[i - 1] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i - 1]] + k * v[i - 1]);
}
}
}
return dp[N][V];
}
int main() {
int N = 5;
int V = 10;
int w[] = {2, 2, 6, 5, 4};
int v[] = {6, 3, 5, 4, 6};
int n[] = {3, 2, 1, 2, 3};
int result = multiple_knapsack(N, V, w, v, n);
printf("Maximum value: %d\n", result);
return 0;
}
在動態規劃中，通?？梢允褂脻L動數組來優化空間復雜度。例如，在0-1背包問題中，可以將二維數組dp[i][j]優化為一維數組dp[j]。
在多重背包問題中，可以通過二進制優化將每種物品的數量n[i]拆分為若干個2的冪次方，從而將多重背包問題轉化為0-1背包問題，提高效率。
本文詳細介紹了如何使用C語言通過動態規劃解決0-1背包問題、完全背包問題和多重背包問題，并提供了相應的代碼實現。通過掌握這些方法，可以有效地解決各種背包問題，并在實際應用中發揮重要作用。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
