★、背包求方案数的时候，多重背包是不行的，因为产生重复的背包会有多种情况。
★、背包记录路径的时候，其实是不行的，因为更新了12的最优解，如果它依赖于6这个背包，然后你后面改变了6这个背包，就GG
1、01背包问题。
tot：总背包空间，vall[i]：每件物品的价值，w[i]：每件物品的重量
http://acm.hdu.edu.cn/showproblem.php?pid=2602
01背包明显可以只写一维的，所以二维的就不写了。
关于为什么可以只写一维的呢？这就和你枚举的顺序有关了。从tot 枚举 到 w[i]。那么是优先更新dp[比较大的数]
而且是从dp[i - 1][]那里更新过来的。至于后面枚举小的背包容量的时候，较大的背包容量是用不了的了，所以这里就可以避免有重复使用的bug。确保都是从dp[i- 1]枚举过来。而这个顺序反转了的话，刚好的完全背包的最优解。这个后面再说
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e3 + ;
int dp[maxn];
int w[maxn], val[maxn];
void work() {
memset(dp, , sizeof dp);
int n, tot;
scanf("%d%d", &n, &tot);
for (int i = ; i <= n; ++i) {
scanf("%d", &val[i]);
}
for (int i = ; i <= n; ++i) {
scanf("%d", &w[i]);
}
for (int i = ; i <= n; ++i) {
for (int j = tot; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j -w[i]] + val[i]);
}
}
printf("%d\n", dp[tot]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
一个常数的优化：
我把tot加大到10000.然后提交就变成了655ms。下面来说说当总背包容量tot比较大的时候，该怎么优化。
对于第n件物品，我们的转移方程是dp[tot] = max(dp[tot], dp[tot - w[n]); //这个就是答案
其实只需要一步就够了，因为我们需要的是dp[tot]，不用再向下枚举了。但是根据上面的代码，是需要枚举到
for (j := tot; j >= w[n]; --j)，是需要枚举到w[n]的，为什么呢？其实是为了给后面的做铺垫。因为我们并不知道这个是最后的一个背包，所以还是需要枚举到w[i]的，因为后面的背包可能需要用到dp[w[i]]这个背包的值。来更新最优解
那么我们可以算出一个下限，什么下限呢，就是后面的所有可能的背包中，最多需要用到那一个背包。
对于最后一个背包，他只需要用到dp[tot - w[n]]这个背包就够了。枚举到倒数第二种物品的时候，
他只需要用到dp[tot - w[n] - w[n - 1]]这个背包就够了。那么前面的背包，我们就不需要更新了。
感觉还是写张图比较好理解，以免我以后忘记。
现在考虑枚举到了倒数第二种物品，我们只需要更新红色那个区域就行了，因为最后一个物品只需要用到dp[tot - w[n]]
那么同理，需要更新红色那段区域，我们只需要知道[tot - w[n] - w[n - 1], tot]这段区域的最优值是谁就可以了，因为我们为了更新红色那段区域，对于倒数第二种物品，其重量是w[i]，下限就是tot - w[n] - w[i]，故按照这个思路递推回去第i件物品即可。
这个用来优化当tot比较大的时候，是有用的，我把tot和w[]都同时加上了一个fix值，结果TLE，不是TLE就是RE。还是找到合适的题目再写上来吧，
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e3 + ;
int dp[maxn];
int w[maxn], val[maxn];
int suffix_sum[maxn];
void work() {
memset(dp, , sizeof dp);
int n, tot;
scanf("%d%d", &n, &tot);
for (int i = ; i <= n; ++i) {
scanf("%d", &val[i]);
}
for (int i = ; i <= n; ++i) {
scanf("%d", &w[i]);
}
suffix_sum[n + ] = ;
for (int i = n; i >= ; --i) {
suffix_sum[i] = w[i] + suffix_sum[i + ];
}
for (int i = ; i <= n; ++i) {
int toUpdate = max(w[i], tot - suffix_sum[i + ]);
for (int j = tot; j >= toUpdate; --j) {
dp[j] = max(dp[j], dp[j -w[i]] + val[i]);
}
}
printf("%d\n", dp[tot]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
一个常数的优化
关于dp的初始化。开始的时候dp[0] = 0表示容量为0的背包，能得到物品的价值是0.后面的就有两类了。
①、需要刚好装满tot个，那么，后面的就是全部都是-inf了，表示刚好刚好装满x个的时候，价值是负的，就是没有价值。
②、不需要的话，就全部都是0.
二维01背包，
POJ 1948
http://poj.org/problem?id=1948
给定n根木棒，要求全部用上，组成一个三角形，使得这个三角形的面积最大。
dp[i][j]表示组成的第一根木棒长度是i的时候，第二根木棒长度是j，第三根木棒的长度是dp[i][j]
那么对于周长是固定的话，那么dp数组开bool的就够了。dp[i][j] = 0表示这个方案不可行
比如dp[0][1] = true。表示第一根木棒是0，第二根木棒是1，第三根是all - 0 - 1。那么就全部木棒也用上了。
转移的话，if (dp[i][j]) then dp[i + val][j] = true; dp[i][j + val] = true;
就是这个物品，可以去两组中的任意一组，都可以。
同样也是枚举顺序的问题，应该倒着来枚举，因为木棒只能用一次。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
bool dp[maxn][maxn];
int a[maxn];
bool check (int a, int b, int c) {
if (abs(a - b) >= c) return false;
if (abs(a - c) >= b) return false;
if (abs(b - c) >= a) return false;
return true;
}
double calc(double a, double b, double c) {
// cout << a << " " << b << " " << c << endl;
double p = (a + b + c) / 2.0;
// cout << p << endl;
double ans = sqrt(p * (p - a) * (p - b) * (p - c));
return ans * ;
}
void work() {
int n;
int all = ;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
all += a[i];
}
// dp[0][0] = dp[a[1]][0] = dp[0][a[1]] = true;
dp[][] = true;
int en = (all + ) / ;
for (int i = ; i <= n; ++i) {
for (int j = en; j >= ; --j) {
for (int k = en; k >= j; --k) {
if (j >= a[i] && dp[j - a[i]][k]) {
dp[j][k] = true;
}
if (k >= a[i] && dp[j][k - a[i]]) {
dp[j][k] = true;
}
}
}
}
int ans = -;
for (int i = ; i <= en; ++i) {
for (int j = i; j <= en; ++j) {
if (dp[i][j] && check(i, j, all - i - j)) {
ans = max(ans, (int)calc(i, j, all - i - j));
}
}
}
printf("%d\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
一题比较好的，具有很强想象力的01背包问题。
题意就是在n个数中，选出一些数字，分成2组，使得两组的和是相同的，现在需要使得这个和最大。
那么可以dp[i][j]表示前i组数中，这两组东西的差值是j的时候，较大的那组数的和是dp[i][j]。那么dp[n][0]是答案
对于每一个物品a[i]，为了产生差值为j时的方案。都有4种情况，
1、不选它，不要了， 那么dp[i][j] = dp[i - 1][j];
2、选择它放去比较矮的那组，那么这个时候，要产生差值是j，需要原本的差值是j + a[i]。而且这个时候，最高的那个值没变化。
3、放去较高的那组，那么这个时候，要产生差值是j，需要原本的差值是j - a[i]，而且他变高了，所以是dp[i - 1][j - a[i]] + a[i]
4、放去较矮的那组，而且超越了本来较高的那组，然后现在的差值是j，这个需要画个图，
为什么会想到这4总情况
因为它是3大类。
1、不用
2、放了之后，最大高度不改变。
3、放了之后，最大高度改变
这时候是，由dp[i - 1][a[i] - j] + j转移过来。
然后取四个的最大值就好了。
这题不容易想啊。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn];
int dp[maxn][ + ];
void work() {
int n;
cin >> n;
for (int i = ; i <= n; ++i) {
cin >> a[i];
assert(a[i] >= );
}
memset(dp, -0x3f, sizeof dp);
dp[][] = ;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= ; ++j) {
if (j >= a[i]) {
dp[i][j] = max(dp[i][j], dp[i - ][j - a[i]] + a[i]); //放去高的
}
if (a[i] >= j) {
dp[i][j] = max(dp[i][j], dp[i - ][a[i] - j] + j);
}
dp[i][j] = max(dp[i][j], dp[i - ][j + a[i]]); //放在小的那里
dp[i][j] = max(dp[i][j], dp[i - ][j]); //不用
}
}
if (dp[n][] <= ) {
cout << "Impossible" << endl;
} else cout << dp[n][] << endl;
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
new:
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
int dp[ + ][ + ];
void work() {
memset(dp, -0x3f, sizeof dp);
int n;
scanf("%d", &n);
int val;
for (int i = ; i <= n; ++i) {
scanf("%d", &val);
dp[i][val] = val;
for (int j = ; j >= ; --j) {
dp[i][j] = max(dp[i][j], dp[i - ][j]);
if (j + val <= ) dp[i][j + val] = max(dp[i][j + val], dp[i - ][j] + val);
if (j >= val) {
dp[i][j - val] = max(dp[i][j - val], dp[i - ][j]);
} else {
dp[i][val - j] = max(dp[i][val - j], dp[i - ][j] - j + val);
}
}
}
// printf("%d\n", dp[2][3]);
if (dp[n][] <= ) {
printf("Impossible\n");
} else printf("%d\n", dp[n][]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
其实这题有一个很简单的方法的，
就是和上面的三角形一样，dp[i][j]表示第一座的高度是i，第二座的高度是j，是否可能。
唉，一开始怎么想不到，不过这个是水过去的，评测机快吧。870ms
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn];
bool dp[ + ][ + ];
void work() {
int n;
cin >> n;
for (int i = ; i <= n; ++i) {
cin >> a[i];
assert(a[i] >= );
}
dp[][] = true;
for (int i = ; i <= n; ++i) {
for (int j = ; j >= ; --j) {
for (int h = ; h >= ; --h) {
// dp[j][h] = dp[j][h] || dp[j - a[i]][h] || dp[j][h - a[i]];
if (j >= a[i]) {
dp[j][h] = dp[j][h] || dp[j - a[i]][h];
}
if (h >= a[i]) {
dp[j][h] = dp[j][h] || dp[j][h - a[i]];
}
}
}
}
for (int i = ; i >= ; --i) {
if (dp[i][i]) {
cout << i << endl;
return;
}
}
cout << "Impossible" << endl;
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
还有这题也不错。 http://www.cnblogs.com/liuweimingcprogram/p/6238454.html
这就是一题暴力题，给定n组数字，每组数字能选出若干个，组成一个和值val。现在需要在这n组中，找出他们共有的和值。
明显对n组都做一次01背包，那么复杂度最坏1e8.但是我还是写了，居然127ms。
这里本来还想用一个常数的优化，但是是不行的，我要生成的是有多少个和值，而不是最优解。
dp[i][j]表示第i组，能否生成j这个和值。然后得到这个数组后，不应该用二分答案。因为有可能有些组没有这个值，然后有一个共同的更大的值。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e2 + ;
bool dp[maxn][maxn * maxn];
vector<int>a[maxn];
int mx[maxn];
//int suffix_sum[maxn][maxn];
int n;
bool check(int val) {
for (int i = ; i <= n; ++i) {
if (!dp[i][val]) return false;
}
return true;
}
void work() {
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
int x;
int sum = ;
while (scanf("%d", &x)) {
if (x == -) break;
a[i].push_back(x);
sum += x;
}
mx[i] = sum;
}
// for (int i = 1; i <= n; ++i) {
// for (int j = a[i].size() - 1; j >= 0; --j) {
// suffix_sum[i][j] = suffix_sum[i][j + 1] + a[i][j];
// }
// }
for (int i = ; i <= n; ++i) {
dp[i][] = true;
}
for (int i = ; i <= n; ++i) {
for (int j = ; j < a[i].size(); ++j) {
// int toUpdate = max(a[i][j], mx[i] - suffix_sum[i][j + 1]);
for (int v = mx[i]; v >= a[i][j]; --v) {
dp[i][v] = dp[i][v] || dp[i][v - a[i][j]];
}
}
}
for (int i = * ; i >= ; --i) {
if (check(i)) {
cout << i << endl;
return;
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
再来一题01背包，这个背包需要检查路径，而且需要检查是否合法。
感觉数据有点水，还不知道我的有没数据卡我的程序。
思路就是看看这n个数字中，有没有一些数字，和值是val。如果有多种情况，就输出-1,不可能，输出0.否则输出方案。
其实记录路径很简单的，这里不说了，主要是怎么确定他有多种解。
比如
18
6
1 2 3 4 5 6
这个是多种解的，3可以用1和2代替。
我的做法是把唯一解分成一组，另外的分成一组，然后两组再进行一次dp，如果能产生相同的数字，就不行，说明可以相互代替了。
dp[v].id，这个背包选了哪一个数字
dp[v].flag，这个背包可以由多少个背包转移过来。
dp[v].pre，这个背包的上一个背包。
说一说这里的小bug
3可以用1 +２代替，也可以用直接一个３来代替。我们选择１ ＋ ２，然后记得标记已经生成了，就是３已经可以生成，不再去记录３的其他路径了。因为，还是上面那个例子。
在更新６的时候，１８ ＝ ６ + １２.是可以得。１２在前面有被生成过。但是，它再次更新了１２.１２ ＝ ６ + ６
这是不合法的，选了两次６了。所以，我们要记录唯一的路径。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int a[];
struct node {
int id, pre;
int flag;
}dp[ * + ];
set<int>ans;
vector<int>one;
vector<int>two;
bool out[ * + ];
bool visone[ * + ];
bool dpone[ * + ];
bool dptwo[ * + ];
void work() {
int tot, n;
cin >> tot >> n;
for (int i = ; i <= n; ++i) {
cin >> a[i];
}
dp[].flag = ;
dp[].id = dp[].pre = inf;
int tim = ;
for (int i = ; i <= n; ++i) {
for (int j = tot; j >= a[i]; --j) {
if (dp[j].flag && dp[j - a[i]].flag) {
dp[j].flag++;
continue;
}
if (dp[j].flag) continue;
if (dp[j - a[i]].flag) {
dp[j].flag++;
dp[j].id = i;
dp[j].pre = j - a[i];
}
}
}
// cout << dp[9].pre << endl;
if (tot == ) {
for (int i = ; i <= n; ++i) {
cout << i << " ";
}
return;
}
// cout << dp[12].id << endl;
if (dp[tot].flag == ) {
cout << << endl;
return;
}
if (dp[tot].flag >= ) {
cout << - << endl;
return;
}
int t = dp[tot].pre;
ans.insert(dp[tot].id);
while (t != ) {
ans.insert(dp[t].id);
t = dp[t].pre;
}
for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) {
out[*it] = true;
one.push_back(*it);
}
for (int i = ; i <= n; ++i) {
if (out[i]) continue;
// cout << i << " ";
two.push_back(i);
}
dpone[] = dptwo[] = true;
for (int i = ; i < one.size(); ++i) {
for (int j = tot; j >= a[one[i]]; --j) {
dpone[j] = dpone[j] || dpone[j - a[one[i]]];
}
}
for (int i = ; i < two.size(); ++i) {
for (int j = tot; j >= a[two[i]]; --j) {
dptwo[j] = dptwo[j] || dptwo[j - a[two[i]]];
if (dptwo[j] && dpone[j]) {
cout << - << endl;
return;
}
}
}
for (int i = ; i < two.size(); ++i) {
cout << two[i] << " ";
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
又傻逼了一次，看了题解。发现别人是直接找它对立的，就是直接找sum - tot就行了。
然后，记录路径，就记录唯一的路径，然后如果有多重解，就可以把解的个数叠加上来。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int a[];
struct node {
int id, pre;
int flag;
}dp[ * + ];
set<int>ans;
vector<int>one;
vector<int>two;
bool out[ * + ];
bool visone[ * + ];
bool dpone[ * + ];
bool dptwo[ * + ];
void work() {
int tot, n;
cin >> tot >> n;
int sum = ;
for (int i = ; i <= n; ++i) {
cin >> a[i];
sum += a[i];
}
dp[].flag = ;
dp[].id = dp[].pre = inf;
tot = sum - tot;
int tim = ;
// cout << tot << endl;
for (int i = ; i <= n; ++i) {
for (int j = tot; j >= a[i]; --j) {
//记录路径，就记录唯一的路径
if (dp[j].flag == && dp[j - a[i]].flag > ) {
dp[j].flag = ;
dp[j].id = i;
dp[j].pre = j - a[i];
}
//如果有多重解
else if (dp[j - a[i]].flag) {
dp[j].flag += dp[j - a[i]].flag;
}
}
}
// cout << dp[110].flag << endl;
if (dp[tot].flag == ) {
cout << << endl;
return;
}
if (dp[tot].flag >= ) {
cout << - << endl;
return;
}
int t = tot;
while (t != ) {
if (dp[t].id == inf) break;
ans.insert(dp[t].id);
t = dp[t].pre;
}
for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) {
cout << *it << " ";
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
dp[j][v]表示前i个物品，刚好用了j个，能否生成v这个价值。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn];
bool dp[ + ][ + ];
struct node {
int a, b;
node(int aa, int bb) : a(aa), b(bb) {}
bool operator < (const struct node & rhs) const {
return (a - b) < (rhs.a - rhs.b);
}
};
set<struct node> ss;
void work() {
int n;
cin >> n;
int sum = ;
for (int i = ; i <= n; ++i) {
cin >> a[i];
sum += a[i];
}
dp[][] = true;
int en = (n) / ;
for (int i = ; i <= n; ++i) {
for (int j = en; j >= ; --j) {
for (int v = sum / ; v >= a[i]; --v) {
dp[j][v] = dp[j][v] || dp[j - ][v - a[i]];
}
}
}
if (n == ) {
cout << << " " << a[] << endl;
return;
}
for (int i = sum / ; i >= ; --i) {
if (dp[en][i]) {
cout << i << " " << sum - i << endl;
return;
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
https://vijos.org/p/1240 01背包的好题。
因为它的状态比较多，比较吓人。（但是这题有错误，夫妻条件不管才能过。）
说说正解吧。
dp[i][j][h][k]表示前i个房间，住了j对夫妻，一共住了h个男的，k个女的这个状态的最小费用。
然后就是暴力枚举每一个房间，更新数组了。
这里有一个很有趣的地方就是，夫妻房最多用1对就已经最优了，因为你用两对的话，可以把他们拆散，2个男的一件，2个女的一件。
所以这里如果考虑夫妻的，是可以卡到你超时的，如果注意到夫妻 只能用一对，那就不会超时。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int dp[ + ][ + ][ + ];
const int maxn = + ;
int a[maxn];
int cost[maxn];
void work() {
int nan, nv, room, toget;
cin >> nan >> nv >> room >> toget;
for (int i = ; i <= room; ++i) {
cin >> a[i] >> cost[i];
}
memset(dp, 0x3f, sizeof dp);
dp[][][] = ;
toget = min(toget, );
toget = ;
for (int i = ; i <= room; ++i) {
for (int j = toget; j >= ; --j) {
for (int h = nan; h >= ; --h) {
for (int k = nv; k >= ; --k) {
if (k >= a[i]) {
dp[j][h][k] = min(dp[j][h][k], dp[j][h][k - a[i]] + cost[i]);
} else {
dp[j][h][k] = min(dp[j][h][k], dp[j][h][] + cost[i]);
}
if (h >= a[i]) {
dp[j][h][k] = min(dp[j][h][k], dp[j][h - a[i]][k] + cost[i]);
} else {
dp[j][h][k] = min(dp[j][h][k], dp[j][][k] + cost[i]);
}
if (j >= && h >= && k >= ) {
dp[j][h][k] = min(dp[j][h][k], dp[j - ][h - ][k - ] + cost[i]);
}
// dp[0][h][k] = min()
}
}
}
}
// cout << dp[0][2][1] << endl;
int ans = inf;
for (int i = ; i <= toget; ++i) {
ans = min(ans, dp[i][nan][nv]);
}
if (ans == inf) {
cout << "Impossible" << endl;
return;
}
cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
2、完全背包
关于完全背包，唯一需要变的就是枚举的方向，使得同一个物品能被多次使用。
http://acm.hdu.edu.cn/showproblem.php?pid=1114
因为需要恰好装满，所以初始化需要改变一下。
完全背包的题目，要求输出最小价值。然后一定要把给出的背包重量全部用完。
就是问一个背包为k的大小，n件物品，能装的最小价值，并且一定是用了k个背包容量。
用dp[i]表示背包容量为i得时候，能收录的最小价值，
边界：dp[0] = 0； 没容量，啥都干不了
else dp[i] = inf。一开始初始化为无穷大。
转移的话,dp[i] = min(dp[i], dp[i - weight[j]] + val[j])
枚举的话，次循环要顺着枚举。
因为这样才能确保它是能使用多次（完全背包嘛）
为什么顺着枚举就可以了呢？
因为考虑一下，当物品的重量为5，背包重量是10的时候。
顺着枚举for (int j = 5; j <= 10; ++j) 的话，
j = 5的时候，物品能枚举到是否加入背包，然后j = 10的时候，物品再次被枚举是否加入这个背包，也就是重复使用了
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int dp[maxn];
int w[maxn];
int val[maxn];
void work() {
int a, b;
scanf("%d%d", &a, &b);
int tot = b - a;
int n;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &val[i], &w[i]);
}
memset(dp, 0x3f, sizeof dp);
dp[] = ;
for (int i = ; i <= n; ++i) {
for (int j = w[i]; j <= tot; ++j) {
dp[j] = min(dp[j], dp[j - w[i]] + val[i]);
}
}
if (dp[tot] == inf) {
cout << "This is impossible." << endl;
} else {
printf("The minimum amount of money in the piggy-bank is %d.\n", dp[tot]);
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
http://www.cnblogs.com/liuweimingcprogram/p/6195469.html 这是一题不错的完全背包
P1159岳麓山上打水
dfsID，第一次听说这东西，但是感觉不太靠谱啊。
一开始的时候，想到了排个序后，然后进行dp，如果要输出字典序最小其实还是可以搞定的，就是2、3、比26小的话，还是可以的。
排序后，只要在转移的时候，如果这个背包有解了的话，就不转移就行了。
但是这题坑爹在需要个数最小，这就不是字典序了。
那么暴力枚举选了多少个桶，那么有2^n种选法。每一种都dp一次。
但是据说，据说在很少步之内就能算出解，然后210ms过了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
bool dp[maxn];
int a[maxn];
int sel[maxn];
int tot, n;
int ans[maxn];
bool dfsID(int cur, int has, int up) {
if (has == up) {
for (int i = ; i <= tot; ++i) dp[i] = false;
dp[] = true;
for (int i = ; i <= has; ++i) {
for (int j = ans[i]; j <= tot; ++j) {
dp[j] = dp[j] || dp[j - ans[i]];
}
}
if (dp[tot]) {
cout << has << " ";
for (int i = ; i <= has; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
return dp[tot];
}
if (cur > n) return false;
if (n - cur + + has < up) return false;
ans[has + ] = a[cur];
return dfsID(cur + , has + , up) || dfsID(cur + , has, up);
}
void work() {
cin >> tot >> n;
assert(tot > );
for (int i = ; i <= n; ++i) {
cin >> a[i];
assert(a[i] > );
}
sort(a + , a + + n);
for (int i = ; i <= n; ++i) {
if (dfsID(, , i)) {
return;
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
work();
return ;
}
3、多重背包问题
有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1086
对于一个物品，如果他有c[i]件，那么我可以把它拆成2^0 + 2^1 + 2^k... + (c[i] - 2^(k + 1) + 1)
这样使得它转化为01背包问题后，任选一些，都能凑合成 <= c[i]的任何数字。
比如14 = 1 + 2 + 4 + 7。只有log个
这样就能结合到1--14之间的所有数字，为什么呢，因为1 + 2 + 4是能组合成1 -- 7之间的任何数字的了，这是根据二进制的思想。
1
10
100
每个东西的位置“1”，都可以要，与不要，所以能组合成1---7的任何数字，然后这些数字和剩下的那个7,一结合，就是1--14的任何数字
然后转化成01背包求解。
复杂度是O(vn)的，现在n有sigma(log(c[i]))个。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
struct node {
int val;
int w;
node(int aa, int bb) : val(aa), w(bb) {}
node() {}
}a[ * + ];
const int maxn = + ;
int dp[maxn];
void work() {
int n, tot;
scanf("%d%d", &n, &tot);
int lena = ;
for (int i = ; i <= n; ++i) {
int w, p, c;
scanf("%d%d%d", &w, &p, &c);
for (int i = ; i <= ; ++i) {
if (( << i) < c) {
c -= ( << i);
a[++lena] = node(( << i) * p, ( << i) * w);
} else {
a[++lena] = node(p * c, w * c);
break;
}
}
}
for (int i = ; i <= lena; ++i) {
for (int j = tot; j >= a[i].w; --j) {
dp[j] = max(dp[j], dp[j - a[i].w] + a[i].val);
}
}
cout << dp[tot] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
这个题目，可以使用上面说的一个常数的优化，使得变成62ms
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
struct node {
int val;
int w;
node(int aa, int bb) : val(aa), w(bb) {}
node() {}
}a[ * + ];
const int maxn = + ;
int dp[maxn];
int suffix_sum[maxn];
void work() {
int n, tot;
scanf("%d%d", &n, &tot);
int lena = ;
for (int i = ; i <= n; ++i) {
int w, p, c;
scanf("%d%d%d", &w, &p, &c);
for (int i = ; i <= ; ++i) {
if (( << i) < c) {
c -= ( << i);
a[++lena] = node(( << i) * p, ( << i) * w);
} else {
a[++lena] = node(p * c, w * c);
break;
}
}
}
for (int i = lena; i >= ; --i) {
suffix_sum[i] = a[i].w + suffix_sum[i + ];
}
for (int i = ; i <= lena; ++i) {
int toUpdate = max(a[i].w, tot - suffix_sum[i + ]);
for (int j = tot; j >= toUpdate; --j) {
dp[j] = max(dp[j], dp[j - a[i].w] + a[i].val);
}
}
cout << dp[tot] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
一个常数的优化
http://codeforces.com/problemset/problem/106/C
4、混合三种背包问题
留坑
5、二维费用背包问题
这类问题就是，对于每一个物品，都有两种不同的费用，a[i]和b[i]，如果选取这个物品，就需要扣除分别的费用，现在给你两种不同的费用的总值，u和v，要求算出在不超过u和v的前提下能得到的最大价值。
所以可以设dp[i][j][k]表示前i种物品，第一种价值的背包容量是j，第二种背包容量是k时，得到的最大值。
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a[i]][k - b[i]] + val[i]);
那么怎么来枚举呢？枚举是有一定的顺序的。
第一，先枚举每件物品，因为每件物品只能选一次，就选能选多次，也是后面维度的枚举顺序要变化。
第二，枚举第三维。
第三，枚举第二维。
为什么需要这样呢？我们结合一个例题
http://acm.tju.edu.cn/toj/showp3596.html
给定n个物品，选出确定的m个，拥有背包容量为L。求最大价值。
设dp[m][L]表示选出了m件物品，背包容量为L时的最大价值。这里我省略了一维
第一，先枚举每件物品，看起来十分好理解，因为不能重新选择嘛。
至于为什么要先枚举第三维，那么我们先来枚举第二维，看看会怎样，结合题目的那个样例。
先枚举选出了k个物品，然后再枚举背包容量为j时得到的最大价值。
for (int i = 1; i <= n; ++i) { //枚举物品
for (int k = 1; k <= min(i, m); ++k) { //枚举在前i个物品中，选了k个
for (int j = L; j >= w[i]; --j) { //枚举背包容量
dp[k][j] = max(dp[k][j], dp[k - 1][j - w[i]] + val[i]);
}
}
}
这样，模拟一下样例的话，是会算重的，dp[1][L]的时候选择了一次物品2，dp[1][L - 物品2的时间]也能选取物品2
那么这个时候dp[2][L] = max(dp[2][L], dp[1][L - 物品2的时间] + val[2])；//这里会算重复。
那么反过来，先枚举背包容量是j，再枚举选出了k件物品。
那么dp[1][L]根据dp[0][L - w[2]]算出，dp[2][L]根据dp[1][L - w[2]]算出，这个时候dp[1][L - w[2]]还没更新，所以不会算重复。
因为题目需要的是一定选出m个，那么dp[0][0...L] = 0，其他是-inf
因为，任何价值的背包，选出0个物品，都是没有价值的。
那为什么dp[1][0...L]是-inf呢。这是为了dp[2][L]从dp[1][]转移过来的时候，不会有价值，因为如果选取不了1个的话，是不能选取到2个的。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int Ti[maxn];
int Vi[maxn];
int dp[maxn][ + ];
void work() {
int n, m, L;
scanf("%d%d%d", &n, &m, &L);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &Ti[i], &Vi[i]);
}
for (int i = ; i <= m; ++i) {
for (int j = ; j <= L; ++j) {
dp[i][j] = -inf;
}
}
for (int i = ; i <= L; ++i) {
dp[][i] = ; //初始化
}
for (int i = ; i <= n; ++i) { //枚举物品为先，只能选一次
for (int j = L; j >= Ti[i]; --j) {
for (int k = ; k <= min(i, m); ++k) {
dp[k][j] = max(dp[k][j], dp[k - ][j - Ti[i]] + Vi[i]);
}
}
}
if (dp[m][L] < ) dp[m][L] = ;
cout << dp[m][L] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
现在发现，上面说的枚举顺序有问题，其实是我对背包问题了解的不透。不好意思了
如果要防止dp[2][L]使用了dp[1][L - w[2]]（已更新）的话，那么可以把m倒着来枚举，这个就是上面的01背包的枚举顺序，因为一开始我觉得m一定是1--min(当前物品个数，m）的嘛，因为i个物品就不能选出m个了。但是倒着枚举，这些都是-inf，是没事的。
下面这个才是二维费用背包的01背包写法。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int Ti[maxn];
int Vi[maxn];
int dp[maxn][ + ];
void work() {
int n, m, L;
scanf("%d%d%d", &n, &m, &L);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &Ti[i], &Vi[i]);
}
for (int i = ; i <= m; ++i) {
for (int j = ; j <= L; ++j) {
dp[i][j] = -inf;
}
}
for (int i = ; i <= L; ++i) {
dp[][i] = ; //初始化
}
for (int i = ; i <= n; ++i) {
for (int k = m; k >= ; --k) {
for (int j = L; j >= Ti[i]; --j) {
dp[k][j] = max(dp[k][j], dp[k - ][j - Ti[i]] + Vi[i]);
}
}
}
if (dp[m][L] < ) dp[m][L] = ;
cout << dp[m][L] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
倒着枚举m
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
int dp[ + ][ + ];
const int maxn = 1e2 + ;
void work() {
memset(dp, -, sizeof dp);
int n, m, L;
scanf("%d%d%d", &n, &m, &L);
for (int i = ; i <= L; ++i) dp[][i] = ;
for (int i = ; i <= n; ++i) {
int w, val;
scanf("%d%d", &w, &val);
for (int j = m; j >= ; --j) {
for (int k = L; k >= w; --k) {
if (dp[j - ][k - w] >= )
dp[j][k] = max(dp[j][k], dp[j - ][k - w] + val);
}
}
}
if (dp[m][L] < ) dp[m][L] = ;
printf("%d\n", dp[m][L]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=2159
二维费用背包 + 多重背包问题。
dp[s][m]表示前i种怪物，最多杀s个怪，拥有m点忍耐度，所得到的最大经验，
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m, k, s;
const int maxn = 1e2 + ;
int dp[maxn][maxn];
int a[maxn];
int b[maxn];
void work() {
memset(dp, , sizeof dp);
for (int i = ; i <= k; ++i) {
scanf("%d%d", &a[i], &b[i]);
}
for (int i = ; i <= k; ++i) {
for (int j = ; j <= s; ++j) {
for (int h = b[i]; h <= m; ++h) {
dp[j][h] = max(dp[j][h], dp[j - ][h - b[i]] + a[i]);
}
}
}
if (dp[s][m] < n) {
printf("-1\n");
} else {
for (int i = ; i <= m; ++i) {
if (dp[s][i] >= n) {
printf("%d\n", m - i);
return;
}
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d%d%d", &n, &m, &k, &s) > ) work();
return ;
}
二维费用背包 + 01背包
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int v[maxn];
int w[maxn];
int val[maxn];
int dp[maxn][maxn];
void work() {
int n;
int totv, totw;
scanf("%d%d", &totv, &totw);
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d%d%d", &v[i], &w[i], &val[i]);
}
for (int i = ; i <= n; ++i) {
for (int j = totv; j >= v[i]; --j) {
for (int k = totw; k >= w[i]; --k) {
dp[j][k] = max(dp[j][k], dp[j - v[i]][k - w[i]] + val[i]);
}
}
}
cout << dp[totv][totw] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
CF:二维费用背包问题，
http://www.cnblogs.com/liuweimingcprogram/p/6226415.html
6、分组背包问题
分组背包，没一个组只能选一个的话，那么设dp[k][v]表示前k组中，背包容量是v时的最大价值
那么转移就是，枚举组k中的每一个新元素，最多只有一个进来，那么就是
dp[k][v] = max(dp[k - 1][v], dp[k - 1][v - w[i]] + val[i])
for () //枚举每一个组
for () //枚举所有背包容量 实质就是说我要更新“当背包是v时，的最大价值”
for () //每一个组的成员
为什么要这个顺序呢，第一枚举每一个组是肯定得。至于第二层，可以这样去想。
因为最多只有一个东西进来，那么枚举背包容量的时候，实质就是说我要更新“当背包是v时，的最大价值”。然后就是更新的问题了。更新的话，就是去这个组中找一个新元素给他。一次的更新只会更新背包容量是v时的最大价值，所以不会影响后面的。
http://acm.hdu.edu.cn/showproblem.php?pid=1712
基本的分组背包。每个物品只选一次
dp[v]表示前k组中，背包容量是v时的最大价值，
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m;
const int maxn = 1e2 + ;
int dp[maxn];
int a[maxn][maxn];
void work() {
memset(dp, , sizeof dp);
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
scanf("%d", &a[i][j]);
}
}
for (int i = ; i <= n; ++i) {
for (int j = m; j >= ; --j) {
for (int k = ; k <= j; ++k) {
dp[j] = max(dp[j], dp[j - k] + a[i][k]);
}
}
}
printf("%d\n", dp[m]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &m) != EOF && (n + m)) work();
return ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=4341
分组背包，每组物品只能取前k件。
关于斜率那里，其实是可以先按斜率排序，然后再按距离原点排序。但是一开始没想到。只会暴力对x排序，对y排序，然后每一个都暴力for一次看看有没相同的斜率，用vector保存。但是这里有x是负数的情况，要把它反转再弄。
然后就是分组背包的套路了
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, T;
const int maxn = + ;
struct node {
int x, y, t, val;
node() {}
node(int xx, int yy, int tt, int vval) : x(xx), y(yy), t(tt), val(vval) {}
bool operator < (const struct node & rhs) const {
if (x != rhs.x) {
return x < rhs.x;
} else return y < rhs.y;
}
}a[maxn], b[maxn];
vector<struct node>gg[maxn];
int dp[ + ];
void work() {
memset(dp, , sizeof dp);
for (int i = ; i <= maxn - ; ++i) {
gg[i].clear();
}
int lena = , lenb = ;
for (int i = ; i <= n; ++i) {
int x, y, t, val;
scanf("%d%d%d%d", &x, &y, &t, &val);
if (x < ) {
b[++lenb] = node(-x, y, t, val);
} else a[++lena] = node(x, y, t, val);
}
sort(a + , a + + lena);
sort(b + , b + + lenb);
for (int i = ; i <= lenb; ++i) {
b[i].x = -b[i].x;
a[++lena] = b[i];
}
assert(lena == n);
int tohash = ;
for (int i = ; i <= n; ++i) {
bool flag = false;
for (int j = ; j <= tohash; ++j) {
if (a[i].y * gg[j][].x == a[i].x * gg[j][].y) {
gg[j].push_back(a[i]);
flag = true;
break;
}
}
if (!flag) {
gg[++tohash].push_back(a[i]);
}
}
// cout << tohash << endl;
for (int i = ; i <= tohash; ++i) {
for (int j = T; j >= ; --j) {
int sumt = , sumval = ;
for (int k = ; k < gg[i].size(); ++k) {
sumt += gg[i][k].t;
sumval += gg[i][k].val;
if (j < sumt) break;
dp[j] = max(dp[j], dp[j - sumt] + sumval);
}
}
}
// printf("%d\n", dp[T]);
static int f = ;
printf("Case %d: %d\n", ++f, dp[T]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &T) != EOF) work();
return ;
}
去写了个对斜率排序的，能排序，关键是y是大于0的，建议大家都写写看，代码比上面的简单不少
其实意思就是，斜率公式本来是y1 / x1的，但是x1可能是0，不能弄。那么我们要对她们斜率排序的话
如果y1 / x1 > y2 / x2的，相当于x1 / y1 < x2 / y2，因为y是大于0的，可以交叉相成。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, T;
const int maxn = + ;
struct node {
int x, y, t, val;
node() {}
node(int xx, int yy, int tt, int vval) : x(xx), y(yy), t(tt), val(vval) {}
bool operator < (const struct node & rhs) const {
int one = x * rhs.y;
int two = rhs.x * y;
if (one != two) {
return one < two;
} return x * x + y * y < rhs.x * rhs.x + rhs.y * rhs.y;
}
bool operator == (const struct node & rhs) const {
return x * rhs.y == rhs.x * y;
}
}a[maxn];
vector<struct node>gg[maxn];
int dp[ + ];
void work() {
memset(dp, , sizeof dp);
for (int i = ; i <= maxn - ; ++i) {
gg[i].clear();
}
for (int i = ; i <= n; ++i) {
scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].t, &a[i].val);
}
int tohash = ;
sort(a + , a + + n);
for (int i = ; i <= n; ++i) {
bool flag = false;
if (tohash > ) {
if (a[i] == gg[tohash][]) {
gg[tohash].push_back(a[i]);
flag = true;
}
}
if (!flag) {
gg[++tohash].push_back(a[i]);
}
}
for (int i = ; i <= tohash; ++i) {
for (int j = T; j >= ; --j) {
int sumt = , sumval = ;
for (int k = ; k < gg[i].size(); ++k) {
sumt += gg[i][k].t;
sumval += gg[i][k].val;
if (sumt > j) break;
dp[j] = max(dp[j], dp[j - sumt] + sumval);
}
}
}
static int f = ;
printf("Case %d: %d\n", ++f, dp[T]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &T) != EOF) work();
return ;
}
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326
并查集后即可
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string> const int maxn = 1e3 + ;
int w[maxn], val[maxn];
int fa[maxn];
int tofind(int x) {
if (x == fa[x]) return x;
else return fa[x] = tofind(fa[x]);
}
void tomerge(int x, int y) {
x = tofind(x);
y = tofind(y);
fa[y] = x;
}
vector<int>gg[maxn];
bool vis[maxn];
int dp[maxn];
void work() {
int n, tot, k;
scanf("%d%d%d", &n, &tot, &k);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &val[i], &w[i]);
fa[i] = i;
}
for (int i = ; i <= k; ++i) {
int a, b;
scanf("%d%d", &a, &b);
tomerge(a, b);
}
for (int i = ; i <= n; ++i) {
gg[tofind(i)].push_back(i);
}
for (int i = ; i <= n; ++i) {
if (vis[tofind(i)]) continue;
vis[tofind(i)] = true;
for (int j = tot; j >= ; --j) {
for (int h = ; h < gg[tofind(i)].size(); ++h) {
if (j < w[gg[tofind(i)][h]]) continue;
dp[j] = max(dp[j], dp[j - w[gg[tofind(i)][h]]] + val[gg[tofind(i)][h]]);
}
}
}
cout << dp[tot] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
http://poj.org/problem?id=3046
这一题的话，想了很久，现在也不知道它究竟属不属于背包问题。
dp[i][j]表示在前i组蚂蚁中，生成长度为j的排列，有多少种可能。
那么，对于第i组，你可以选择1个、2个、....N[i]个
选择一个的话，那么可以在前i - 1组中，选择j - 1个，加上这一个，就是dp[i][j]的一个贡献。
直接转移复杂度是n * m * m，但是也能过题目，可以先直接转移，再用前缀和优化。
记得有MOD数的。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = * * + ;
int dp[maxn];
const int MOD = 1e6;
int book[ + ];
set<int>ss;
int pre[maxn];
void work() {
int n, m, L, R;
cin >> n >> m >> L >> R;
int tot = ;
for (int i = ; i <= m; ++i) {
int x;
cin >> x;
book[x]++;
ss.insert(x);
}
for (set<int> :: iterator it = ss.begin(); it != ss.end(); ++it) {
tot += book[*it];
}
dp[] = ;
for (int i = ; i <= tot; ++i) pre[i] = ;
int now = ;
for (set<int> :: iterator it = ss.begin(); it != ss.end(); ++it) {
int x = *it;
now += book[x]; //最多能产生这么长的序列
for (int i = now; i >= ; --i) { //01背包，要倒着枚举
int en = min(i, book[x]);
// for (int j = 1; j <= en; ++j) { //这个组，选多少个进来
// dp[i] += dp[i - j];
// dp[i] %= MOD;
// }
int up = pre[i - ];
int down;
if (i - en == ) down = ;
else down = pre[i - en - ];
dp[i] += (up - down + MOD) % MOD;
dp[i] %= MOD;
}
pre[] = ;
for (int j = ; j <= tot; ++j) {
pre[j] = (dp[j] + pre[j - ]) % MOD;
}
}
int ans = ;
for (int i = L; i <= R; ++i) {
// cout << dp[i] << endl;
ans += dp[i];
if (ans >= MOD) ans %= MOD;
}
cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
P1198最佳课题选择
一开始还以为这题是泛化物品背包，然后去看背包9讲，很是抽象，不能领会，然后就自己YY，最后发现居然是简单的分组背包。
开始我是这样想的，如果要写n篇，那么第一种， 我可以写1、2、4...2^k篇，就是用上面的二进制思想，多重背包的思想。那么01背包后，就能得到第一种选多少篇来写了。然而有bug，因为如果写3篇的话，a * 3^b和a * 1^b + a * 2^b往往是不等价的。
那么我就干脆暴力，每一种都有可能写0、1、2、3、....n，每一组中，只选一个，那么就是标准的分组背包了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
struct node {
LL val;
int w;
node(int ww, LL vval) : w(ww), val(vval) {}
};
vector<struct node>gg[ + ];
LL calc(int a, int b, int x) {
LL ans = ;
for (int i = ; i <= b; ++i) {
ans *= x;
}
ans *= a;
return ans;
}
LL dp[];
void work() {
// cout << calc(100, 5, 200) << endl;
int n, m;
cin >> n >> m;
for (int i = ; i <= m; ++i) {
int a, b;
cin >> a >> b;
for (int j = ; j <= n; ++j) {
gg[i].push_back(node(j, calc(a, b, j)));
}
}
for (int i = ; i <= - ; ++i) {
dp[i] = 1e17L;
}
dp[] = ;
for (int i = ; i <= m; ++i) {
for (int v = n; v >= ; --v) {
for (int j = ; j < gg[i].size(); ++j) {
if (v >= gg[i][j].w) {
dp[v] = min(dp[v], dp[v - gg[i][j].w] + gg[i][j].val);
}
}
}
}
cout << dp[n] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
work();
return ;
}
7、有依赖的背包问题。
P1313金明的预算方案
如果像这题一样，附件没有了其他附件的话，其实这题还是很好做的。
首先，用个vector[i]表示第i件主件有多少件附件，就是所有附件都push_back了，然后，对于没组的主件，都来一个01背包。
这样就知道在第i组中，拥有v的背包，能得到最大的价值是多少。
可以用一个明显的优化就是物廉价美的东西才要，贵的，而且价值不高的，就可以舍弃，这样使得物品数大大减少。
然后对于每一组，来一个分组背包就好了。
关于01背包的时候，怎么规定它一定要选了主件后，才能选一个附件呢？
我的做法是把附件的cost和val都加上主件的cost和val。这样使得选取了某一个附件的时候，隐含地选取了一个主件。
但是这样有bug，就是选择了两件附件的时候，这样就隐含地选了两个主件了，所以，判断选物品进来的时候，如果它本来已经有物品的了，那么，就应该减去主件的cost和主件的val了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
struct node {
int w, val;
node(int ww, int vval) : w(ww), val(vval) {}
};
vector<struct node>vc[maxn];
vector<struct node>gg[maxn];
int mx[maxn][ + ];
int dpZeroOne[maxn][ + ];
int dp[ + ];
void work() {
int tot, n;
cin >> tot >> n;
for (int i = ; i <= n; ++i) {
int a, b, which;
cin >> a >> b >> which;
if (which == ) {
vc[i].push_back(node(a, a * b));
} else {
vc[which].push_back(node(a + vc[which][].w, a * b + vc[which][].val));
}
}
for (int i = ; i <= n; ++i) {
if (vc[i].size() == ) continue;
for (int j = ; j < vc[i].size(); ++j) {
for (int h = tot; h >= vc[i][j].w; --h) {
if (dpZeroOne[i][h] == ) {
dpZeroOne[i][h] = max(dpZeroOne[i][h], dpZeroOne[i][h - vc[i][j].w] + vc[i][j].val);
} else {
dpZeroOne[i][h] = max(dpZeroOne[i][h], dpZeroOne[i][h - vc[i][j].w + vc[i][].w] + vc[i][j].val - vc[i][].val); //减多了一次
}
}
}
for (int j = ; j <= tot; ++j) {
if (dpZeroOne[i][j] == ) continue;
if (mx[i][j] >= dpZeroOne[i][j]) {
mx[i][j + ] = mx[i][j];
continue;
}
mx[i][j] = dpZeroOne[i][j];
mx[i][j + ] = mx[i][j];
gg[i].push_back(node(j, mx[i][j]));
}
}
for (int i = ; i <= n; ++i) {
if (gg[i].size() == ) continue;
// cout << i << "£º" << endl;
// for (int j = 0; j < gg[i].size(); ++j) {
// cout << gg[i][j].w << " " << gg[i][j].val << endl;
// }
for (int v = tot; v >= ; --v) {
for (int j = ; j < gg[i].size(); ++j) {
if (v >= gg[i][j].w) {
dp[v] = max(dp[v], dp[v - gg[i][j].w] + gg[i][j].val);
}
}
}
}
cout << dp[tot] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
work();
return ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=3449
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int n, tot;
struct node {
int w, val;
node(int ww, int vval) : w(ww), val(vval) {}
};
int each[maxn];
vector<struct node>vc[maxn];
vector<struct node>gg[maxn];
int dp[ + ];
int mx[ + ];
void work() {
for (int i = ; i <= n; ++i) {
vc[i].clear();
gg[i].clear();
int x, num;
scanf("%d%d", &x, &num);
each[i] = x;
for (int j = ; j <= num; ++j) {
int w, val;
scanf("%d%d", &w, &val);
vc[i].push_back(node(w + x, val));
}
}
for (int i = ; i <= n; ++i) {
memset(dp, , sizeof dp);
for (int j = ; j < vc[i].size(); ++j) {
for (int h = tot; h >= vc[i][j].w; --h) {
if (dp[h]) {
dp[h] = max(dp[h], dp[h - vc[i][j].w + each[i]] + vc[i][j].val);
} else dp[h] = max(dp[h], dp[h - vc[i][j].w] + vc[i][j].val);
}
}
memset(mx, , sizeof mx);
for (int j = ; j <= tot; ++j) {
if (dp[j] == ) {
mx[j + ] = mx[j];
continue;
}
if (mx[j] >= dp[j]) {
mx[j + ] = mx[j];
continue;
}
mx[j + ] = dp[j];
gg[i].push_back(node(j, dp[j]));
}
// for (int j = 0; j < gg[i].size(); ++j) {
// cout << gg[i][j].w << " " << gg[i][j].val << endl;
// }
}
memset(dp, , sizeof dp);
for (int i = ; i <= n; ++i) {
if (gg[i].size() == ) continue;
for (int v = tot; v >= ; --v) {
for (int j = ; j < gg[i].size(); ++j) {
if (v >= gg[i][j].w) {
dp[v] = max(dp[v], dp[v - gg[i][j].w] + gg[i][j].val);
}
}
}
}
cout << dp[tot] << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &tot) > ) work();
return ;
}