DP
朴素的写法
直接上代码,详细注释,保证可以看懂!
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], dp[N][N]; // 状态表示 f(i, j) 表示i件物品,体积为j的情况下的最大价值
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
// 初始状态
// f(0, x) 没有选物品,不管容量有多少总的价值为零
// f(x, 0) 能选x件物品,但是容量为0,放不进去价值也是零
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
// 状态转移 我们需要考虑的就是放不放这件物品
// 不放这件物品 f(i - 1, j) -> f(i, j)
// 放这件物品,还需要判断能不能放下 f(i - 1, j - vi) + wi -> f(i, j)
dp[i][j] = dp[i - 1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << dp[n][m];
return 0;
}
滚动数组优化
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], dp[N]; // 状态表示 f(j) 体积为j的情况下的最大价值
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
for(int i = 1; i <= n; ++ i)
for(int j = m; j >= v[i]; -- j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m];
return 0;
}
滚动数组简单来说就是,我们每次只用到了上一次的状态,本次循环开始的时候,状态还没有更新,数组就是上一次的状态。
但是本题有个需要注意的地方,观察朴素版本的状态转移
$$if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);$$
我们还用到了本层的状态,由于$j - v[i] < j$是一定的,我们可以从后往前枚举,这样一来从后面往前更新数组,$j$会比$j - v[i]$的状态更早更新。这意味着$j$的达到了本层的状态,$j - v[i]$的状态还是上一层的。
DFS
未优化(暴力深搜)
#include <iostream>
using namespace std;
const int N = 10010;
int v[N], w[N];
int n, m, wmax;
int dfs(int i, int cur_v, int cur_w){
if(i > n){
return cur_w;
}
if(cur_v + v[i] <= m){
return max(dfs(i + 1, cur_v + v[i], cur_w + w[i]), dfs(i + 1, cur_v, cur_w));
}else{
return dfs(i + 1, cur_v, cur_w);
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> v[i] >> w[i];
}
wmax = dfs(1, 0, 0); // 从第一个数开始枚举
cout << wmax;
return 0;
}
剪枝版本
#include <iostream>
using namespace std;
const int N = 10010;
int v[N], w[N], tmp[N][N]; // tmp的含义是在某个位置i,体积为vi的重量
int n, m, wmax;
int dfs(int i, int cur_v, int cur_w){
if(i > n){
return cur_w;
}
if(cur_v + v[i] <= m){
// 减枝
if(tmp[i][cur_v] > cur_w + w[i]) return tmp[i][cur_v];
tmp[i][cur_v] = cur_w + w[i];
return max(dfs(i + 1, cur_v + v[i], cur_w + w[i]), dfs(i + 1, cur_v, cur_w));
}else{
if(tmp[i][cur_v] > cur_w) return tmp[i][cur_v];
tmp[i][cur_v] = cur_w;
return dfs(i + 1, cur_v, cur_w);
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> v[i] >> w[i];
}
wmax = dfs(1, 0, 0); // 从第一个数开始枚举
cout << wmax;
return 0;
}
一看时间,弱爆了哈哈哈,就当练习了。