zoj 3164 쿠키 초이스(혼합 패키지 그룹)
Time Limit: 2 Seconds
Memory Limit: 32768 KB
MM enjoyed cookies very much. On Saint Valentine's Day, when she stepped into a big cookie store again, she wouldn't leave unless DD spent all his money in pocket!
There are N kinds of cookies, labeled from 1 to N, and all can be bought without any restriction by the store. But actually, for some kinds of cookies, MM wanted to buy one piece at most, and for some kinds of cookies, MM wanted to buy Ki pieces at most, and for some other kinds of cookies, there didn't exist an upper bound that MM wanted to buy.
There is another requirement from MM: there are some groups of cookies, MM considered their tastes similar, so she wanted to buy at most one kind of cookies in each group. A kind of cookie wouldn't appear in more than one group.
For the ith kind of cookies, MM has an "enjoyable value" Ei, if DD bought Ai pieces of this kind for her, and Ai didn't exceed her upper bound, MM get EiAi of enjoyable value. After buying cookies, MM's total enjoyable value will be the sum of EiAi.
But actually, poor DD had only D dollars, and the price for the ith kind of cookies is Pi dollars per piece. DD must spend all his D dollars to buy cookies, to meet requirements about amount and taste from MM, and to make MM's enjoyable value as high as possible. What's more, as you know, a legal plan's enjoyable value must be non-negative.
Input
There are multiple test cases. Each test case consists of three parts.
The first part is one line with two integers N and D.
The second part has N lines, line i consists of three integers Ki, Ei and Pi. If Ki equals to 0, it means for ith kind of cookies, there didn't exist an upper bound that MM wanted to buy, otherwise Ki is the upper bound for ith kind of cookies.
The third part describes the groups. A non-negative integer G represents the number of groups, and then G lines, each line consists of some integers represents labels of kinds of cookies in this group.
One blank line between test cases.
Output
If the proper and optimal plan exists, output the maximal total enjoyable value ΣEiAi, otherwise output "i'm sorry...".
Output one line per text case.
Data Restriction 1 <=
N <= 1024, 0 <=
D <= 1024.
0 <=
Ki <= 1024, -1024 <=
Ei <= 1024, 0 <
Pi <=
D.
0 <=
G <= 8.
All numbers referred are integers.
Number of test cases is no more than 80.
Sample Input
2 1024
0 1 3
0 0 1
0
10 1023
1 1 1
1 1 2
1 1 4
1 1 8
1 1 16
1 1 32
1 1 64
1 1 128
3 -1 256
1 1 512
1
9 10
10 1023
1 1 1
1 1 2
1 1 4
1 1 8
1 1 16
1 1 32
1 1 64
1 1 128
1 1 256
1 1 512
1
9 10
Sample Output
341
5
i'm sorry...
제목:
너에게 약간의 물품과 약간의 돈을 주겠다. 모든 물품은 가치, 개수, 가격이 있다. 그리고 물품은 조를 나눌 수 있다. 각 조의 물품은 하나라도 더 가져가서 이 돈을 다 쓰고 얻은 최대 가치를 묻는다.
아이디어:
전형적인 그룹 혼합 가방 문제.처음 만들었는데 다른 사람의 코드를 참고했으니 혼합배낭과 조별배낭을 먼저 알고 만들어야 한다.
코드:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 2005
#define MAXN 16005
#define mod 1000000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,ans,cnt,tot,flag;
int f[maxn],dp[maxn];
int k[maxn],e[maxn],p[maxn];
int gro[maxn],w[10][maxn]; // w[i][j]- i j
char s[maxn];
void ZeroOnePack(int cost,int val,int tmp[])
{
for(int i=m;i>=cost;i--)
{
tmp[i]=max(tmp[i],tmp[i-cost]+val);
}
}
void CompletePack(int cost,int val,int tmp[])
{
for(int i=cost;i<=m;i++)
{
tmp[i]=max(tmp[i],tmp[i-cost]+val);
}
}
void MultiplePack(int cost,int val,int num,int tmp[])
{
int i,j,t=0;
for(j=0; ;j++)
{
t+=(1<<j);
if(t>=num) break ;
ZeroOnePack((1<<j)*cost,(1<<j)*val,tmp);
}
t-=(1<<j);
t=num-t;
ZeroOnePack(t*cost,t*val,tmp);
}
bool solve()
{
int i,j,t,g;
memset(dp,-INF,sizeof(dp));
memset(w,-INF,sizeof(w));
int OO=dp[0];
dp[0]=0;
for(i=1;i<=n;i++)
{
if(gro[i]) // dp f w
{
memset(f,-INF,sizeof(f));f[0]=0;
}
if(!k[i]||k[i]*p[i]>=m)
{
CompletePack(p[i],e[i],gro[i]?f:dp);
}
else
{
MultiplePack(p[i],e[i],k[i],gro[i]?f:dp);
}
if(gro[i])
{
for(j=0;j<=m;j++) w[gro[i]][j]=max(w[gro[i]][j],f[j]);
}
}
for(int g=1;g<=cnt;g++) // w[i][j] 01
{
for(i=m;i>=1;i--)
{
for(j=1;j<=i;j++)
{
if(dp[i-j]>OO&&w[g][j]>OO) dp[i]=max(dp[i],dp[i-j]+w[g][j]);
}
}
}
ans=dp[m];
if(ans<0) return false ;
return true ;
}
int main()
{
int i,j,t;
while(~scanf("%d%d",&n,&m))
{
for(i=1; i<=n; i++)
{
scanf("%d%d%d",&k[i],&e[i],&p[i]);
}
memset(gro,0,sizeof(gro));
scanf("%d",&cnt);
gets(s);
for(i=1; i<=cnt; i++)
{
gets(s);
for(j=0; s[j]!='\0';)
{
if(s[j]>='0'&&s[j]<='9')
{
t=0;
while((s[j]>='0'&&s[j]<='9'))
{
t=t*10+s[j]-'0';
j++;
}
gro[t]=i;
}
else j++;
}
}
if(solve()) printf("%d
",ans);
else printf("i'm sorry...
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.