01背包问题
代码1:(二维朴素做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N]; // dp[0][0] = 0
int v[N],w[N];
int n,m;
int main(){
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 = 0;j <= m;j++){
dp[i][j] = dp[i-1][j];
if (j - v[i] >= 0){
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}
}
cout << dp[n][m];
return 0;
}
代码2:(一维滚动数组优化)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N];
int n,m;
int v,w;
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++){
cin >> v >> w; // 边输入边处理
for (int j = m;j >= v;j--){
dp[j] = max(dp[j],dp[j-v]+w);
}
}
cout << dp[m];
return 0;
}
完全背包问题
代码1:三重循环(朴素)做法,数据加强后TLE
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int dp[N][N];
int v[N],w[N];
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> v[i] >> w[i];
// i从1开始枚举,j从0开始枚举
for (int i = 1;i <= n;i++)
for (int j = 0;j <= m;j++)
for (int k = 0;k*v[i]<=j;k++)
dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]] + k*w[i]);
cout << dp[n][m] << endl;
return 0;
}
代码2:(二维优化做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int dp[N][N];
int v[N],w[N];
int main(){
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 = 0;j <= m;j++){
dp[i][j] = dp[i-1][j];// 特判第一种情况
if (j >= v[i]) dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
cout << dp[n][m] << endl;
return 0;
}
代码3:(第一维度优化做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int dp[2][N];
int v,w;
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++){
cin >> v >> w;
for (int j = 0;j <= m;j++){
dp[i&1][j] = dp[(i-1)&1][j];
if (j >= v) dp[i&1][j] = max(dp[i&1][j],dp[i&1][j-v] + w);
}
}
cout << dp[n&1][m] << endl;
return 0;
}
代码4:(滚动数组优化做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int dp[N];
int v[N],w[N];
int main(){
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 = v[i];j <= m;j++){
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
cout << dp[m] << endl;
return 0;
}
多重背包问题
代码1:(三维朴素做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N];
int v[N],w[N],s[N];
int n,m;
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1;i <= n;i++){
for (int j = 0;j <= m;j++){
// 比完全背包多一个物品件数限制
for (int k = 0;k <= s[i] && j >= k*v[i];k++) dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]] + k*w[i]);
}
}
cout << dp[n][m] << endl;
return 0;
}
代码2:(二进制优化做法)
#include <iostream>
#include <algorithm>
using namespace std;
// N的上限是n*logS == 1000*log2000
// M表示背包物品总体积不超过2010
const int N = 12000,M = 2010;
int n,m;
int v[N],w[N];
int dp[M];
int main(){
cin >> n >> m;
int cnt = 0;// 重新分组
for (int i = 1;i <= n;i++){
int a,b,s;
cin >> a >> b >> s;
int k = 1;
while (k <= s){
cnt++;//组别先增加,下标从1开始
v[cnt] = a*k;//整体体积
w[cnt] = b*k;// 整体价值
s -= k;
k *= 2;// k = 1,2,4,8,...
}
// 处理最后的剩余一组
if (s > 0){
cnt ++;
v[cnt] = a*s;
w[cnt] = b*s;
}
}
n = cnt;//枚举次数由个数变成重新划分的组别数
// 求解优化后的01背包问题
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] << endl;
return 0;
}
分组背包问题
代码1:(二维朴素做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m;
int dp[N][N];
int v[N][N],w[N][N],s[N];
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++){
cin >> s[i];
for (int j = 0;j < s[i];j++){
cin >> v[i][j] >> w[i][j];
}
}
for (int i = 1;i <= n;i++)
for (int j = 0;j <= m;j++){
dp[i][j] = dp[i-1][j];// 不选
for (int k = 0;k < s[i];k++){// 选第k件
if (j >= v[i][k]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k]] + w[i][k]);
}
}
cout << dp[n][m] << endl;
return 0;
}
代码2:(一维滚动数组优化做法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m;
int v[N][N],w[N][N],s[N];
int dp[N];
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++){
cin >> s[i];
for (int j = 0;j < s[i];j++){
cin >> v[i][j] >> w[i][j];
}
}
for (int i = 1;i <= n;i++)
// 逆序枚举j
for (int j = m;j >= 0;j--){
for (int k = 0;k < s[i];k++){
// if判断不能放在for的条件判断里面,相当于break
if (j >= v[i][k]) dp[j] = max(dp[j],dp[j-v[i][k]] + w[i][k]);
}
}
cout << dp[m] << endl;
return 0;
}