思路 DFS –> 记忆化搜索 –> DP
第一种DFS写法
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int res = 0;
void dfs(int u, int sumV, int sumW)
{
if(u > n)
{
if(sumV <= m && sumW >= res)
{
res = sumW;
}
return ;
}
//不选
dfs(u + 1, sumV, sumW);
//选
if(sumV + v[u] <= m)
dfs(u + 1, sumV + v[u], sumW + w[u]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i = 1; i <= n; i ++)
{
cin>>v[i]>>w[i];
}
dfs(1, 0, 0);
cout<<res;
return 0;
}
第二种DFS写法
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int res = 0;
int dfs(int u, int spv)
{
if(u > n)
{
return 0;
}
else if(spv < v[u])
{
return dfs(u + 1, spv);
}
else if(spv >= v[u])
{
return max(dfs(u + 1, spv), dfs(u + 1, spv - v[u]) + w[u]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i = 1; i <= n; i ++)
{
cin>>v[i]>>w[i];
}
int res = dfs(1, m);
cout<<res;
return 0;
}
记忆化搜索,这个题能用记忆化搜索AC!!!
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int res = 0;
int mem[N][N];
//为什么这里写记忆化搜索不继续用sumW这个参数呢?
/*
1.sumW对边界无影响
2.如果dfs传入三个参数,mem就需要开三维分别记录u,spv,sumW,这个题目的数据是1000,会爆内存
*/
int dfs(int u, int spv)
{
if(mem[u][spv]) return mem[u][spv];
int sum = 0;
if(u > n)
{
sum = 0;
}
else if(spv < v[u])
{
sum = dfs(u + 1, spv);
}
else if(spv >= v[u])
{
sum = max(dfs(u + 1, spv), dfs(u + 1, spv - v[u]) + w[u]);
}
mem[u][spv] = sum;
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i = 1; i <= n; i ++)
{
cin>>v[i]>>w[i];
}
int res = dfs(1, m);
cout<<res;
return 0;
}
DP
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i = 1; i <= n; i ++)
{
cin>>v[i]>>w[i];
}
for(int i = n; i >= 1; i --)
for(int j = 1; j <= m; j++)
{
if(j < v[i]) // 如果背包不够装
f[i][j] = f[i + 1][j];
else if(j >= v[i])
f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
}
cout<<f[1][m];
return 0;
}
时间复杂度:
DFS:O(2^n)
记忆化搜索:O(nv)