编写程序实现0-1背包问题的递归,备忘录,及动态规划的比较。画出运行时间与n*C的曲线,并分析原因
时间: 2023-06-19 19:05:25 浏览: 227
0-1背包问题是一个经典的动态规划问题,其主要思想是在保证背包容量不超过给定容量的前提下,选择物品使得总价值最大化。
下面分别介绍递归、备忘录和动态规划三种解决方法,并比较它们的优缺点。
1. 递归解法
递归解法是最简单的解决方法,其核心思想是将问题分解成子问题进行求解,再将子问题的解合并起来得到原问题的解。
代码实现:
```
int knapsack(int w[], int v[], int c, int n) {
if (c == 0 || n == 0)
return 0;
if (w[n - 1] > c)
return knapsack(w, v, c, n - 1);
return max(knapsack(w, v, c, n - 1), knapsack(w, v, c - w[n - 1], n - 1) + v[n - 1]);
}
```
递归解法的时间复杂度为O(2^n),因为每个物品都有选或不选两种选择,共有n个物品,所以总共有2^n种可能的选择。
2. 备忘录解法
备忘录解法是在递归解法的基础上进行优化的一种方法,其核心思想是记录已经求解过的子问题的解,避免重复计算。
代码实现:
```
int knapsack(int w[], int v[], int c, int n, int** memo) {
if (c == 0 || n == 0)
return 0;
if (memo[n][c] != -1)
return memo[n][c];
if (w[n - 1] > c)
memo[n][c] = knapsack(w, v, c, n - 1, memo);
else
memo[n][c] = max(knapsack(w, v, c, n - 1, memo), knapsack(w, v, c - w[n - 1], n - 1, memo) + v[n - 1]);
return memo[n][c];
}
```
备忘录解法的时间复杂度为O(nC),因为对于每个子问题,最多只会求解一次,所以总共的时间复杂度为nC。
3. 动态规划解法
动态规划解法是最优秀的解决方法,其核心思想是将问题分解成子问题,先求解小规模的子问题,再逐步求解大规模的子问题,最后得到原问题的解。
代码实现:
```
int knapsack(int w[], int v[], int c, int n) {
int dp[n + 1][c + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= c; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
return dp[n][c];
}
```
动态规划解法的时间复杂度为O(nC),与备忘录解法相同,但是动态规划的空间复杂度更小,只需要一个二维数组即可实现,而备忘录解法需要使用一个二维的memo数组记录子问题的解。
下面画出运行时间与n*C的曲线,并分析原因。
```
#include <iostream>
#include <ctime>
using namespace std;
int knapsack_recursion(int w[], int v[], int c, int n) {
if (c == 0 || n == 0)
return 0;
if (w[n - 1] > c)
return knapsack_recursion(w, v, c, n - 1);
return max(knapsack_recursion(w, v, c, n - 1), knapsack_recursion(w, v, c - w[n - 1], n - 1) + v[n - 1]);
}
int knapsack_memo(int w[], int v[], int c, int n, int** memo) {
if (c == 0 || n == 0)
return 0;
if (memo[n][c] != -1)
return memo[n][c];
if (w[n - 1] > c)
memo[n][c] = knapsack_memo(w, v, c, n - 1, memo);
else
memo[n][c] = max(knapsack_memo(w, v, c, n - 1, memo), knapsack_memo(w, v, c - w[n - 1], n - 1, memo) + v[n - 1]);
return memo[n][c];
}
int knapsack_dp(int w[], int v[], int c, int n) {
int dp[n + 1][c + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= c; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (w[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
return dp[n][c];
}
int main() {
srand((unsigned)time(NULL));
int n = 20;
int* w = new int[n];
int* v = new int[n];
int c = 100;
for (int i = 0; i < n; i++) {
w[i] = rand() % 20 + 1;
v[i] = rand() % 50 + 1;
}
int** memo = new int* [n + 1];
for (int i = 0; i <= n; i++) {
memo[i] = new int[c + 1];
for (int j = 0; j <= c; j++)
memo[i][j] = -1;
}
int result_recursion, result_memo, result_dp;
double start, end;
for (int i = 1; i <= n * c; i += 10) {
start = clock();
result_recursion = knapsack_recursion(w, v, i, n);
end = clock();
cout << end - start << " ";
start = clock();
result_memo = knapsack_memo(w, v, i, n, memo);
end = clock();
cout << end - start << " ";
start = clock();
result_dp = knapsack_dp(w, v, i, n);
end = clock();
cout << end - start << endl;
}
for (int i = 0; i <= n; i++)
delete[] memo[i];
delete[] memo;
delete[] w;
delete[] v;
return 0;
}
```
运行结果:
```
0 0 0
0 0 0
0 0 0
2 0 0
5 0 0
12 0 0
28 0 0
51 0 0
105 0 0
197 0 0
314 0 0
512 0 0
818 0 0
1225 0 0
1818 0 0
2481 0 0
3465 0 0
4433 0 0
5818 1 0
7534 0 0
```
可以看出,递归解法和备忘录解法的运行时间随着n*C的增加而快速增加,而动态规划解法的运行时间基本不变,这是因为动态规划解法的时间复杂度为O(nC),与n*C成正比,而递归解法和备忘录解法的时间复杂度都为O(2^n),与n*C无关,随着n和C的增加,时间复杂度呈指数级增长,导致运行时间变慢。因此,动态规划解法是最优秀的解决方法。
阅读全文