背包九讲
本帖最后由 798236606 于 2020-3-5 10:17 编辑测试平台：https://www.acwing.com/problem/
1.01背包
解：
二维DP
dp表示前i个物品在剩余空间为j的情况下能够装的最大价值量（不一定恰好装满），其中dp必须初始化为0（因为前0个物品的价值量肯定为0）
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
int n, m;
int dp;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
int v, w;
cin >> v >> w;
for (int j = 0; j <= m; ++j)//如果装不下，则继承i - 1的结果,若装的下则考虑装与不装哪个更赚
dp = (j < v) ? dp : max(dp, dp + w);
}
cout << dp << endl;
return 0;
}
【注】大多数一维DP做起来很困难，此时升到二维会简单很多
一维DP
dp表示当前物品与之前的物品（其实还是前i个物品）在剩余空间为j的情况下能够装的最大价值量（不一定恰好装满），其中dp必须初始化为0（因为前0个物品的价值量肯定为0）
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
int n, m;
int dp;
int main(void)
{
cin >> n >> m;
while (n--)
{
int v, w;
cin >> v >> w;
//装不下的情况不用管，会自然地继承上一次的计算结果，每次计算只是对上次计算的加工处理。j从后往前保证每个物品只被计算一次
for (int j = m; j >= v; --j) dp = max(dp, dp + w);
}
cout << dp << endl;
return 0;
}
2.完全背包
解：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
int n, m;
int dp;
int main(void)
{
cin >> n >> m;
while (n--)
{
int v, w;
cin >> v >> w;
//j从前往后保证每个物品可以被计算多次
for (int j = v; j <= m; ++j) dp = max(dp, dp + w);
}
cout << dp << endl;
return 0;
}
其实还有一种更容易想到的解法：枚举每件物品的选取个数（其实把问题转化成了01背包）
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
int n, m;
int dp;
int main(void)
{
cin >> n >> m;
while (n--)
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; --j)
for (int k = 1; k * v <= j; ++k)
dp = max(dp, dp + k * w);
}
cout << dp << endl;
return 0;
}
3.多重背包Ⅰ
解:
类似于上一题的第二种解法
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e2 + 10;
int n, m;
int dp;
int main(void)
{
cin >> n >> m;
while (n--)
{
int v, w, t;
cin >> v >> w >> t;
for (int j = m; j >= v; --j)
for (int k = 1; k <= t && k * v <= j; ++k)
dp = max(dp, dp + k * w);
}
cout << dp << endl;
return 0;
}
但是当数据较大时效率就会比较差，此时使用二进制优化法
4.多重背包Ⅱ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e3 + 5;
typedef struct GOOD{
int v, w;
GOOD (int _v, int _w) : v(_v), w(_w) {};
}Good;
int n, m;
int dp;
vector<Good> goods;
int main(void)
{
cin >> n >> m;
while (n--)
{
int v, w, t;
cin >> v >> w >> t;
for (int k = 1; k <= t; t -= k, k *= 2)
goods.push_back(GOOD(k * v, k * w));
if (t) goods.push_back(GOOD(t * v, t * w));
}
for (auto good: goods)
for (int j = m; j >= good.v; --j)
dp = max(dp, dp + good.w);
cout << dp << endl;
return 0;
}
未完待续。。。 多谢！
页:
[1]