01背包
有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。
第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，\(N，V\)，用空格隔开，分别表示物品数量和背包容积。
接下来有 \(N\) 行，每行两个整数 \(v_i,w_i\)，用空格隔开，分别表示第 \(i\) 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
\(0<N,V≤1000\)
\(0<v_i,w_i≤1000\)
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
题意
给出n个有体积有价值的物品，任意选取物品组合使得在背包容量有限条件下(m)总价值最大
特点
- 每个物品只能选一次
- 取最大值
dfs
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1010;
int n,m,V,W,cnt;
int v[N],w[N],ans[N];
void dfs(int x){
if(x > n){
ans[++cnt] = W;
return;
}
if(V >= v[x]){ //选(注意是>=而不是>)
V -= v[x];
W += w[x];
dfs(x + 1);
V += v[x];
W -= w[x];
}
dfs(x + 1); //不选
}
void solve(){
cin >> n >> m;
V = m;
for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];
dfs(1);
int res = 0;
for(int i = 1; i <= cnt; i ++)res = max(res,ans[i]);
cout << res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
结果： Segmentation Fault
通过了 4/12个数据
原因：在程序运行过程中，如果递归调用的层数过多，会因为系统分配的栈空间溢出引发错误 -> 递归改成递推
许多步骤重复计算了！！！ -> 记忆化搜索完善
dp
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1010;
int n,m;
int v[N],w[N],f[N][N];
//f[i][j]记录剩余容积为i时选前j个物品的最大值
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++){
f[i][j] = f[i][j - 1]; //不选
if(i >= v[j])f[i][j] = max(f[i][j-1],f[i-v[j]][j-1]+w[j]); //选
}
}
cout << f[m][n];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
结果： Accepted
运行时间： 78 ms
运行空间： 4188 KB
优化
点击查看代码
void solve(){
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 --){ //容量在下
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
cout << f[m];
}
结果： Accepted
运行时间： 40 ms
运行空间： 216 KB