一层一层剥开背包问题
程序员文章站
2022-06-22 17:33:13
背包问题是非常经典的动态规划问题,这里设计到空间开销的问题,以下对方法不断改进,优化空间开销。1.记忆化搜索时间复杂度: O(n * C) 其中n为物品个数; C为背包容积空间复杂度: O(n * C)#include <iostream>#include <vector>#include <cassert>using namespace std......
背包问题是非常经典的动态规划问题,这里设计到空间开销的问题,以下对方法不断改进,优化空间开销。
1.记忆化搜索
时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
空间复杂度: O(n * C)
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/// 背包问题
/// 记忆化搜索
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(n * C)
class Knapsack01{
private:
vector<vector<int>> memo;
// 用 [0...index]的物品,填充容积为c的背包的最大价值
int bestValue(const vector<int> &w, const vector<int> &v, int index, int c){
if(c <= 0 || index < 0)
return 0;
if(memo[index][c] != -1)
return memo[index][c];
int res = bestValue(w, v, index-1, c);
if(c >= w[index])
res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
memo[index][c] = res;
return res;
}
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert(w.size() == v.size() && C >= 0);
int n = w.size();
if(n == 0 || C == 0)
return 0;
memo.clear();
for(int i = 0 ; i < n ; i ++)
memo.push_back(vector<int>(C + 1, -1));
return bestValue(w, v, n - 1, C);
}
};
- 动态规划
时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
空间复杂度: O(n * C)
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/// 背包问题
/// 动态规划
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(n * C)
class Knapsack01{
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert(w.size() == v.size() && C >= 0);
int n = w.size();
if(n == 0 || C == 0)
return 0;
vector<vector<int>> memo(n, vector<int>(C + 1,0));
for(int j = 0 ; j <= C ; j ++)
memo[0][j] = (j >= w[0] ? v[0] : 0 );
for(int i = 1 ; i < n ; i ++)
for(int j = 0 ; j <= C ; j ++){
memo[i][j] = memo[i-1][j];
if(j >= w[i])
memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
}
return memo[n - 1][C];
}
};
3.动态规划改进: 滚动数组
时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
空间复杂度: O©, 实际使用了2*C的额外空间
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/// 背包问题
/// 动态规划改进: 滚动数组
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(C), 实际使用了2*C的额外空间
class Knapsack01{
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert(w.size() == v.size() && C >= 0);
int n = w.size();
if( n == 0 && C == 0 )
return 0;
vector<vector<int>> memo(2, vector<int>(C + 1, 0));
for(int j = 0 ; j <= C ; j ++)
memo[0][j] = (j >= w[0] ? v[0] : 0);
for(int i = 1 ; i < n ; i ++)
for(int j = 0 ; j <= C ; j ++){
memo[i % 2][j] = memo[(i-1) % 2][j];
if(j >= w[i])
memo[i % 2][j] = max(memo[i % 2][j], v[i] + memo[(i-1) % 2][j - w[i]]);
}
return memo[(n-1) % 2][C];
}
};
4.动态规划改进
时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
空间复杂度: O©, 只使用了C的额外空间
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert(w.size() == v.size() && C >= 0);
intn = w.size();
if(n == 0 || C == 0)
return 0;
vector<int> memo(C+1,0);
for(int j = 0 ; j <= C ; j ++)
memo[j] = (j >= w[0] ? v[0] : 0);
for(int i = 1 ; i < n ; i ++)
for(int j = C ; j >= w[i] ; j --)
memo[j] = max(memo[j], v[i] + memo[j - w[i]]);
return memo[C];
}
};
本文地址:https://blog.csdn.net/weixin_38246633/article/details/85985991
上一篇: CentOS7 设置yum源