## zoj 3164 Cookie choice 解题报告

2019年02月09日 算法 ⁄ 共 2122字 ⁄ 字号 评论关闭

刚看完题，对于 MM的 another requirement 有点疑问。she want to buy one kind of cookies in each group。

解题思路：

每种物品有个值 K ，K非零时， 代表有购买上线即做完全背包，K为零时代表无购买上线即做多重背包。

```for i : 1 -> n
begin
if( blong[i] ) // 是否属于某个group
clear( tmp );
if( k[i] )
MultiplePack( blong[i]?tmp:dp );
else
CompletePack( blong[i]?tmp:dp );
if( blong[i] )
for j : 1 -> d
group[ blong[i] ][ j ] = max( group[ blong[i] ][ j ] , tmp[ j ] );//对分组背包的预处理
end```

```for groupID : 1 -> g
for i : d -> 0
for j : 1 -> i
dp[ i ] = max( dp[i] , dp[i-j] + group[groupID][j] );```

贴上AC代码

```#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define INF 0x3fffffff
#define MAXN 1125

int dp[ MAXN ] , tmp[ MAXN ] , group[ 10 ][ MAXN ];
int n , d , g , blong[ MAXN ] , k[ MAXN ] , e[ MAXN ] , p[ MAXN ];

void ZeroOnePack( int cost , int wight , int f[] ){
for( int i = d ; i >= cost ; --i )
f[i] = max( f[i] , f[i-cost] + wight );
}
void CompletePack( int cost , int wight , int f[] ){

for( int i = cost ; i <= d ; ++ i )
f[i] = max( f[i] , f[ i-cost ] + wight );
}
void MultiplePack( int cost , int wight , int amount , int f[] ){

if( cost * amount >= d ){
CompletePack( cost , wight , f );
return ;
}
int k = 1 ;
while( k < amount ){
ZeroOnePack( cost * k , wight * k , f );
amount -= k ;
k <<= 1 ;
}
ZeroOnePack( cost * amount , wight * amount , f );

}

bool get( int gid ){

int x = 0 ;
char ch;
while( ch = getchar() ){
if( ch == ' ' || ch == '\n' ){
blong[ x-1 ] = gid ;
//printf( " %d" , x );
return ch != '\n' ;
}
x = x*10 + ( ch - '0' ) ;
}
}

void clear( int f[] ){
for( int i = 1 ; i <= d ; ++ i )
f[i] = -INF;
f[0] = 0 ;
}

int main()
{
while( ~scanf( "%d%d" , &n , &d ) ){

for( int i = 0 ; i < n ; ++ i )
{
scanf( "%d%d%d" , &k[i] , &e[i] , &p[i]  ) ;
blong[i] = 0;
}
scanf( "%d" , &g );getchar();
for( int i = 1 ; i <= g  ; ++ i ) {
clear( group[i] );
while( get( i ) );
}
clear( dp );

for( int i = 0 ; i < n ; ++ i ){
if( blong[i] ) clear( tmp );
if( k[i] )
MultiplePack( p[i] , e[i] , k[i] ,  blong[i]?tmp:dp );
else
CompletePack( p[i] , e[i] , blong[i]?tmp:dp );
if( blong[i] )
for( int j = 1 ; j <= d ; ++ j )
group[ blong[i] ][ j ] = max( group[ blong[i] ][ j ] , tmp[j] );
}
for( int gid = 1 ; gid <= g ; ++ gid ){
for( int i = d ; i >= 0 ; -- i ){
for( int j = 1 ; j <= i ; ++ j ){
dp[i] = max( dp[i] , dp[i-j] + group[gid][j]);
}
}
}
if( dp[d] >= 0 ) printf( "%d\n" , dp[d] );
else puts( "i'm sorry..." );

}
return 0;
}

```

【上篇】
【下篇】