一.P3985 不开心的金明(01背包变式)
解析:
一开始没有看数据范围,直接当01背包直接写了,结果最后4个测试点RE,一看到数据范围就老实了,1e9的数据,数组直接炸,所以不能直接使用一维的01背包.看了一下题解,部分人是通过极差对数据进行分类,按照300进行分开,使用贪心和dp一起做.
我认为有些麻烦了,我们之所以不能通过一维01背包来实现就是因为数据范围太大,但如果我们可以将数据范围减少,那我们依然可以通过01背包实现.因为极差最大为3,我们只要将所有数据都减去其中的最小值,那么物品的价格的范围就被缩到0~3了,为了方便使用,我们可以都加上1,让范围从一开始,从而最后总的价格也就被控制在1000以内.但由于,我们是把所有物品的价格都减去最小值,那我们在尝试放入背包时就要再在加上判断,以此我们要在加上一维,再在dp数组中多加一维，记录一共选了几个.dp[i][j]表示我选的修改后的物品的选了i个,价格为j.
代码实现:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[1005][1005], w[N], v[N];
ll a, b, c, n, m, t;
ll ans, sum, num, minn=1e9+7, maxx;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
minn = min(minn, w[i]);
}
minn--;
sum = 0;
for (int i = 1; i <= n; i++) {
w[i] -= minn;
sum += w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = sum; j >= w[i]; j--) {
for (int k = n; k >= 1; k--) {
if (k * minn + j <= m)
dp[k][j] = max(dp[k][j], dp[k-1][j - w[i]] + v[i]);
}
}
}
ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
}
二.P5662 [CSP-J2019] 纪念品(完全背包变形)
解析:
这道题的关键在于如何将抽象的问题转换成我们熟悉的模型:
这是一道完全背包的题，我们进行 𝑡−1 轮完全背包:
把今天手里的钱当做背包的容量，
把商品今天的价格当成它的消耗,
把商品明天的价格当做它的价值，
每一天结束后把总钱数加上今天赚的钱，直接写背包模板即可。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], p[105][105];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx;
int main()
{
cin >> t >> n >> m;
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= n; j++) {
cin >> p[i][j];
}
}
for (int i = 1; i < t; i++) {
memset(dp, 0, sizeof(dp));
for (int j = 1; j <= n; j++) {
for (int k = p[i][j]; k <= m; k++) {
dp[k] = max(dp[k], dp[k - p[i][j]] + p[i + 1][j] - p[i][j]);
}
}
m += dp[m];
}
cout << m << endl;
return 0;
}P5020 [NOIP2018 提高组] 货币系统(完全背包变形)
解析:
将a数组从小到大排序,最小的数必须要选，然后利用完全背包的思想，从𝑎𝑖ai到最大值筛选一遍，将可以组成的打上标记,在判断后面的数字时，如果已经被标记过了，就不再选，没有被标记过就标记一下，再筛选一次数(即一次完全背包)
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], vis[N];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
int main()
{
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
maxx = max(maxx, w[i]);
}
memset(vis, 0, sizeof(vis));
sort(w + 1, w + 1 + n);
ans = 0;
for (int i = 1; i <= n; i++) {
if (vis[w[i]])
continue;
ans++;
vis[w[i]] = 1;
for (int j = w[i]; j <= maxx; j++) {
vis[j] = max(vis[j], vis[j - w[i]]);
}
}
cout << ans << endl;
}
return 0;
}
