背包问题整理帖,更新中..
这里物品的2种属性我这样描述: 花费，亦负重，为w[]数组。价值为v[]数组。
dp[i][j]为从[0,i]号物品中取，在j负重的限制下的最大价值。
下面3种情形很遗憾都没去解释怎么推导的，权当笔记，以后再补全吧(笑。
最简单的0-1背包：
// 其中N为物品种类数 M是总负荷
int w[maxN], v[maxN];
int dp[maxN];
for (int i = 0; i < N; ++i)
for (int j = M; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
多重背包:
// 务必注意数组要开得要够大
// 一般为N*logC 其中N是种类 C是某种类最大个数
// M为容量
int N, M;
int w[maxN], v[maxN], dp[maxN];
int tw, tv, tc;
for (int i = 0; i < N; ++i) {
scanf("%d%d%d", &tw, &tv, &tc);
int t = 1;
while (tc >= t) {
v[cnt] = tv * t;
w[cnt] = tw * t;
tc -= t;
t *= 2;
++cnt;
}
if (tc == 0)
continue;
v[cnt] = tv * tc;
w[cnt] = tw * tc;
++cnt;
}
memset(dp, 0, sizeof(dp));
for (int i = 0; i < cnt; ++i)
for (int j = M; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
printf("%d", dp[M]);
完全背包
int w[maxN], v[maxN];
int dp[maxN];
for (int i = 0; i < N; ++i)
for (int j = w[i]; j <= M; ++j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
这里参考这篇博客把这些背包问题都刷了一遍。这里做下笔记：
hdu 2602
Bone Collector: 裸的01背包。不解释..
hdu 2546
饭卡：这里提到但凡卡上的剩余金额>=5，就一定可以购买成功,即使之后的余额为负，否则无法购买。首先如果卡不够5元，直接输出即可。否则：这里得贪心地“钻个空子“，先拿出5元去买最贵的菜，剩下的以金额-5为负重限制进行0-1背包。
最终结果就是原来的金额 - 买到的总的菜的价值了。
hdu 2955
给出一个能承受的被抓的最大风险，给出N个银行能劫得的金钱量和被抓风险(一个概率值)，问在能承受的风险值内，最多可劫得多少钱?
主要问题在于物品的花费是浮点数，常规的0-1背包不可行。我们不如把风险概率转成安全概率。安全概率=1-风险概率。
这里有个小地方：抢不同银行的安全概率是各个银行安全概率之积，而风险概率却不能这样算，这是要这样转化的原因，能利用乘法计算要选多个银行时的安全概率。
最终方法是：将求最小安全概率限制下的最大价值问题，转化成求一定价值下的最大安全概率问题。那么答案将是：满足最低安全概率的最大下标(即价值)。注意这里容量取所有银行钱数之和，因为没给劫匪抢多少钱的容量限制，这是自己找到的限制。
抽象来说：是从求负重限制下的最大价值，变成了求价值限制下的最小负重(这里是最大安全值，即最小危险值)。
// 将概率容量下的最大价值 转化成求一定价值下的安全概率
// 那么安全概率>要求的安全概率的最大价值即是所得
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
const int inf=0x3f3f3f3f, maxN=1e5+5;
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
ll w[maxN], M = 0, N;
double v[maxN], dp[maxN], P;
scanf("%lf %lld", &P, &N);
FOR(i, 0, N) {
scanf("%lld%lf", &w[i], &v[i]); v[i] = 1 - v[i];
M += w[i];
}
memset(dp, 0, sizeof dp);
dp[0] = 1;
FOR(i, 0, N)
for(ll j = M + 1; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] * v[i]);
ll ans = -inf;
FOR(i, 0, M + 1)
if (dp[i] > (1 - P))
ans = max(ans, i);
printf("%lld\n", ans);
}
return 0;
}
hdu 1203
I NEED A OFFER! 也是一道花费为浮点数的问题。你有N万美元，M所可选的学校。每所学校有各自的申请费用A和得到这个学校offer的可能性P。问可以收到至少一份offer的最大概率。这个时候可以从做编程题的角度跳出来，回到初高中看问题的角度..问至少拿一所offer的概率，我们最方便的计算方式当然是求没有一个offer的概率，最后以‘一’减得答案了。
和上一题差不多，我们不能拿浮点数来做“花费(负重)"的限制，问题转化成：在花费限制下的得不到offer的最小概率。
抽象来说：是从求负重限制下的最大价值，变成了求价值限制下的最小负重(这里即最小被拒概率)。
这里有个小插曲:当时就想：为啥上一题的容量限制是所有银行金钱之和，这里却不是所有学校收费之和? 因为上一题没有给出“最多可以抢多少钱”，我们只能自己找容量上限。而这题已经给出了你手上只有N万美元，所以拿这个作为限制即可，更多也没有意义。
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
const int maxM=1e5+5;
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int N, M, v[maxM];
double w[maxM], dp[maxM];
while (~scanf("%d%d", &N, &M) && (N + M)) {
FOR(i, 0, M) {
scanf("%d%lf", &v[i], &w[i]);
w[i] = 1.0 - w[i];
}
fill(dp, dp + maxM, 1.0);
FOR(i, 0, M) {
RFOR(j, v[i], N + 1) {
dp[j] = min(dp[j], dp[j - v[i]] * w[i]);
cout << dp[j] <<" "<< dp[j - v[i]] * w[i] << endl;;
}
cout << endl;
}
FOR(i, 0, N+1)
printf("%.1lf%%\n", (dp[N]) * 100);
printf("\n--\n");
printf("%.1lf%%\n", (1.0 - dp[N]) * 100);
}
return 0;
}
hdu 1171
Big Event in HDU
把所有物品分成A、B 2部分，要求2部分的价值尽可能相等，并保证金额A >= B
多重背包，给出了N个物品的价值和数量。要求均分。先求得所有物品的总价值，取其半作为负重限制，那么求得的最大值即B部分的价值，A自然是总价值-B的金额。
留意个地方：是以负数作为终止条件，而非-1。
// 多重背包，问把一些物品平分
// 取总价值之半为容量计算即可
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RFOR(i,a,b) for(ll i=(b);i>=(a);--i)
using namespace std;
ll N, dp[250005], v[250005];
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
while(~scanf("%lld", &N) && N >= 0) {
ll newN = 0, sum = 0;
FOR(i, 0, N) {
ll val, cnt;
scanf("%lld%lld", &val, &cnt);
sum += val * cnt;
ll t = 1;
while (cnt >= t) {
v[newN++] = t * val;
cnt -= t;
t *= 2;
}
if (cnt == 0) continue;
else v[newN++] = cnt * val;
}
memset(dp, 0, sizeof dp);
ll M = sum / 2;
FOR(i, 0, newN)
RFOR(j, v[i], M)
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
printf("%lld %lld\n", sum - dp[M], dp[M]);
}
return 0;
}
hdu 2639
Bone Collector II
求0-1背包的第K大解。菜鸡第一次遇到这种问题，看了很多博客，看懂的是这个，思路整理如下：
我们用完滚动数组，状态变成dp[j],其实我们的dp[j]相当于每次都从dp[i-1][j]和dp[i-1][j-w[i]]+v[i]中取了最大值。就是每次从2个状态中挑最大值。
里面有个比喻:如果我想知道年级最高分，那么，我只要知道每个班级的最高分，然后挑最高的。如果我想知道年级前10呢？我必须要知道每个班的前10名。然后合并、挑选，过程中再取前10，大家在心里模拟一下，对，这就是本题核心的算法。两种决策，就可以看作这个年级只有两个班。
dp[i+1][j][k]表示dp[i+1][j]状态下第k大解。显然dp[i+1][j]这个含有k个元素的数组是一个递增序列。(是否严格递增按题意来，这题里是严格的)
dp[i+1][j][k]，我们每次都从上2个班，即dp[i][j][k]和dp[i][j-w[i]][k]+w[i]，这2k个人中，挑最大的k个人合并更新到dp[i+1][j][k]中，形成dp[i+1][j][k]的前k优解，那么我们最终的答案即dp[M][k].M是物品种类数。 下面的程序中，我们拿2个数组A和B，表示上2个班的前k名情况，最后合并出新k名，放到状态dp[j][k]中
// 0-1背包第k优解
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RFOR(i,a,b) for(ll i=(b);i>=(a);--i)
using namespace std;
int T, N, M, K;
int dp[10005][35], v[10005], w[10005];
int A[10005], B[10005];
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &N, &M, &K);
memset(dp, 0, sizeof dp);
FOR(i, 0, N) scanf("%d", &v[i]);
FOR(i, 0, N) scanf("%d", &w[i]);
FOR(i, 0, N) {
RFOR(j, w[i], M + 1) {
FOR(k, 1, K + 1)
A[k] = dp[j][k], B[k] = dp[j - w[i]][k] + v[i];
A[K + 1] = B[K + 1] = -1;
int a = 1, b = 1, cnt = 1;
while (cnt <= K && (A[a] != -1 || B[b] != -1)) {
if (A[a] > B[b]) dp[j][cnt] = A[a++];
else dp[j][cnt] = B[b++];
if (dp[j][cnt] != dp[j][cnt - 1]) ++cnt;
}
}
}
printf("%d\n", dp[M][K]);
}
return 0;
}
这里挖个坑，找时间来梳理一下“完全背包”的公式推导过程，解释为什么只是和0-1背包循环方向相反。
其实：整理这些问题也花了一些时间的，但是写出来博客的时候却精简得“很不友好”。也难怪自己看别人博客的时候老是觉得：wc，你就这样一笔带过？这么多“显然”，这么多“易得”，真是一篇shit..右上角再见。现在也有点理解别人了..东西懂了之后就觉得不难，也往往觉得别人也容易理解似的，或者说是懒得好好去梳理。后者还好些，前者就不好了..大概就是懂了之后，以至于他忘记了当他不懂时所遇到的困难。容易给人留下不友好的印象....(瞎说中..)如果我博客哪里不好懂了,可以留言踩一下,说不定我解释的过程中发现自己也其实不懂(⊙_⊙)?
