一、朴素的爆搜
01背包的普通爆搜版
//输入
4 5
2 3
1 2
3 4
2 2
//输出
7每种情况选或不选。这里给出没看书前自己写的。
#include <iostream>
#include <stdio.h>
#include <vector>
void init() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
using namespace std;
typedef pair<int, int> PII;
const int N = 1020;
PII a[N];
int maxn = 0;
int n, k;
void dfs(int u, int sum, int v) { //下标 总价值 总体积
if (u == n)
{
if(v <= k)
maxn = max(maxn, sum);
return;
}
dfs(u + 1, sum + a[u].second, v + a[u].first);
dfs(u + 1, sum, v);
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second; //weight val
dfs(0, 0, 0);
cout << maxn;
return 0;
}这是一点儿优化也没有的搜索，运行过程中极有可能会出现重复计算。
想到用数组记录状态。我一直认为dp能把数组的状态想对题目就做出来了一半。
按照书上的思路再写一遍dfs，这次的dfs减少了一个参数。将递归函数返回一个值。
依然是没有优化的爆搜，为之后的数组表示状态做准备。
#include <iostream>
#include <stdio.h>
#include <vector>
void init() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
using namespace std;
const int N = 1020;
int w[N], v[N];
int maxn = 0;
int n, k;
int dfs(int u, int j) { //下标 剩余体积
int res;
if (u == n) { //搜不下去了
res = 0;
}
else if (j < w[u]) { //放不下当前的
res = dfs(u + 1, j);
}
else { //放得下当前的 两种情况都试下
res = max(dfs(u + 1, j), dfs(u + 1, j - w[u]) + v[u]);
}
return res;
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; //weight val
cout << dfs(0, k);
return 0;
}二、记忆化搜索
然后我们加上记忆化数组dfs搜索。啥是记忆化数组？用数组记录某个状态、当程序需要用到这个状态时：如果有直接返回数字；如果没有更新。某种意义上也是拿空间换时间的一种策略。
这里的dfs参数有两个：下标和剩余体积。有没有可能用到之前出现过的状态呢？答案是有，因为dfs有回溯。
用空间换时间后的代码如下（其实就是稍加改进，联想斐波那契数列的数组推导）：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
void init() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
using namespace std;
const int N = 1020;
int w[N], v[N]; //体积 价值
int dp[N][N]; //用空间换时间
int maxn = 0;
int n, k;
int dfs(int u, int j) { //下标 剩余体积
if (dp[u][j] > 0) return dp[u][j];
int res;
if (u == n) { //搜不下去了
res = 0;
}
else if (j < w[u]) { //放不下当前的
res = dfs(u + 1, j);
}
else { //放得下当前的 两种情况都试下
res = max(dfs(u + 1, j), dfs(u + 1, j - w[u]) + v[u]);
}
return dp[u][j] = res;
}
int main()
{
init();
memset(dp, -1, sizeof dp);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; //weight val
cout << dfs(0, k);
return 0;
}改进版本的核心是数组表示状态。
用这个方式来表示下：令dp[i][j] 表示 从第 i 个物品开始挑选、总重量小于等于 j 时，总价值的最大值
然后我们写下代码：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
void init() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
using namespace std;
const int N = 1020;
int w[N], v[N];
int dp[N][N]; //用空间换时间
int maxn = 0;
int n, k;
//dp[i][j] 表示 从第i个物品开始挑选、总重量小于等于j时，总价值的最大值
void solve() {
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
if (j < w[i]) {
dp[i][j] = dp[i + 1][j];
}
else {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
}
//if (dp[i][j] > 0) cout << i << ' ' << j << endl;
}
}
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; //重量 价值
solve();
cout << dp[0][k];
return 0;
}在上一个程序中我们逆着表示的。改变状态表示意义尝试下：令dp[i][j] 表示 挑选到第 i-1 个物品、总重量小于等于 j 时，总价值的最大值。
自己试着实现了下，用的偏移量防止数组访问下标 -1
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
void init() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
using namespace std;
const int N = 1020;
int w[N], v[N];
int dp[N][N]; //用空间换时间
int maxn = 0;
int n, k;
//dp[i][j] 表示 挑选到第 i-1 个物品、总重量小于等于 j 时，总价值的最大值
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (j < w[i-1]) { //i-1偏移量
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]); //i-1是偏移量
}
}
}
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; //重量 价值
solve();
cout << dp[n][k];
return 0;
}同样的状态表示换一个推导方程：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
void init() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
using namespace std;
const int N = 1020;
int w[N], v[N];
int dp[N][N]; //用空间换时间
int maxn = 0;
int n, k;
//dp[i+1][j] 表示 选到 i, 总体积不超过 j
void solve() {
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= k; j++) {
if (j < w[i]) {
dp[i + 1][j] = dp[i][j];
}
else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; //重量 价值
solve();
cout << dp[n][k];
return 0;
}三、实例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 220;
LL dp[N][N]; //dp[i+1][j]表示 选择i, 一共选了j 偏移一位
LL a[N];
int main()
{
memset(dp, -0x3f, sizeof dp);
int n, k, x; cin >> n >> k >> x; //k是窗口 选x个
for (int i = 1; i <= n; i ++ ) cin >> a[i];
dp[0][0] = 0;
for (int i = 1; i <= n; i ++){
for(int j = 1; j <= x; j ++){ //x是次数
//再搞一个向前搜索
for(int m = max(0, i - k); m < i; m ++){
dp[i][j] = max(dp[i][j], dp[m][j-1] + a[i]);
}
}
}
LL res = -1;
for(int i = n - k + 1; i <= n; i ++) res = max(res, dp[i][x]);
cout << res;
return 0;
}