HDU3535AreYouBusy(分组背包)

http://acm.hdu.edu.cn/showproblem.php?pid=3535

分组背包,每一组加了以下三个限制

            0 stands for the sets that should choose at least 1 job to do,
1 for the sets that should choose at most 1 ,
2 for the one you can choose freely

HDU3535AreYouBusy(分组背包)

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R typedef long long LL;
const double eps = 1e-;
const int MAXN = ;
const int MAXM = ; int n, T, m, s;
int DP[][];
int cost[], val[]; int main()
{
while(~scanf("%d%d", &n, &T))
{
for(int i=;i<=T;i++) DP[][i]=;
for(int i=;i<=n;i++)
{
scanf("%d%d", &m, &s);
for(int j=;j<m;j++) scanf("%d%d", &cost[j], &val[j]);
if(s==) {
for(int k=;k<=T;k++) DP[i][k] = -INF;// 这样确保最少放一个物品
for(int j=;j<m;j++)
for(int k=T;k>=cost[j];k--) {
//** 如果是第一次选,则一定能加入数组中
//** 如果不是第一次选,则当做普通01背包处理
DP[i][k] = max(DP[i][k], max(DP[i][k-cost[j]]+val[j], DP[i-][k-cost[j]]+val[j]));
}
}
else if(s==) {
// 为了保证全局最优解,初始化为上一次结果
for(int k=;k<=T;k++) DP[i][k] = DP[i-][k];
for(int j=;j<m;j++)
for(int k=T;k>=cost[j];k--) {
DP[i][k] = max(DP[i][k], DP[i-][k-cost[j]]+val[j]);
}
}
else if(s==) {
for(int j=;j<=T;j++)DP[i][j] = DP[i-][j];
for(int j=;j<m;j++)
for(int k=T;k>=cost[j];k--) {
DP[i][k] =max(DP[i][k], max(DP[i-][k-cost[j]]+val[j], DP[i][k-cost[j]]+val[j]));
}
}
}
printf("%d\n", max(DP[n][T], -));
}
return ;
}
上一篇:nginx自动检测后台服务器健康状态


下一篇:Python使用requests模块下载图片