 /**//*
题意:给出一些物品,有价值,数量,价格
还有一些限制,限制的组里面只能选一种物品,问D钱最多能获得的价值

按组分阶段,然后根据物品数量分别做0-1,完全,多重背包(logn)

之前做的都是一维数组的背包,换成滚动数组时注意更新的顺序!!!

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cctype>

using namespace std;

const int MAXN = 1030;
const int INF = 1000000000;

int price[MAXN] , num[MAXN] , val[MAXN];
int dp[2][MAXN] , _dp[MAXN];
vector<int> group[MAXN];
bool vi[MAXN];
char str[10000];

int main()
  {
//freopen("in","r",stdin);

int n , D;
while( ~scanf("%d%d",&n,&D) )
 {
group[0].clear();
for(int i = 1 ; i <= n ; i++)
 {
group[i].clear();
vi[i] = false;
scanf("%d%d%d" , &num[i] , &val[i] , &price[i]);
}

int G;
scanf("%d\n",&G);
for(int i = 0 ; i < G ; i++)
 {
gets(str);
for(int j = 0 ;str[j] ; )
 {
if(isdigit(str[j]))
 {
int x = 0;
while(isdigit(str[j]))
x = 10*x + str[j++]-'0';
group[i].push_back(x);
vi[x] = true;
}
else j++;
}
}

for(int i = 1 ; i <= n ; i++)
 {
if(vi[i])continue;
group[G++].push_back(i);
}
int pre = 0 , now = 1;
dp[pre][0] = 0;
for(int i = 1 ; i <= D; i++)
dp[pre][i] = -INF;
for(int i = 0 ; i < G ; i++)
 {
dp[now][0] = 0;
for(int j = 1 ; j <= D; j++)
dp[now][j] = -INF;
for(int ii = 0 ; ii < group[i].size() ; ii++)
 {
int id = group[i][ii];

if(num[id] == 1)//0-1 pack
 {
for(int j = price[id] ; j <= D; j++)
dp[now][j] = max(dp[now][j] , dp[pre][j-price[id]] + val[id]);
}
else if(num[id] == 0)//complete pack
 {
for(int j = 0 ; j <= D; j ++)//多开一个数组
_dp[j] = dp[pre][j];
for(int j = price[id] ; j <= D; j++)
 {
_dp[j] = max(_dp[j] , _dp[j-price[id]] + val[id]);
dp[now][j] = max(dp[now][j] , _dp[j]);
}
}
else//
 {
for(int j = 0 ; j <= D; j ++)//多开一个数组
_dp[j] = dp[pre][j];
int amount = num[id] , k = 1;
while(amount > 0)
 {
if(k>amount)k = amount;
amount -= k;
for(int j = D ; j >= k*price[id] ; j--)//注意是在新的基础上_dp[j]
 {
_dp[j] = max(_dp[j] , _dp[j-k*price[id]] + k*val[id]);
dp[now][j] = max(dp[now][j] , _dp[j] );
}
k<<=1;
}
}
}
for(int j = 0 ; j <= D; j++)//记得要更新!!
dp[now][j] = max(dp[now][j] , dp[pre][j]);
swap(pre,now);
}
if(dp[pre][D] < 0)puts("i'm sorry ");
else printf("%d\n",dp[pre][D]);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|