学步园

这题的作者 CUI, Tianyi, 也就是《背包九讲》的作者 崔天翼 。该题整合了几中典型的背包。所以能完全独立的状况下AC这道题。那么背包问题也就不是问题了。

首先膜拜下大神。 瞻仰下  Jane Street Capital。

下面是解题报告正文：

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

刚开始的理解是只买一个。再阅读一遍后 才看到重点是 kind  一种cookie。侧面反映了阅读尚需提高。

 解题思路：

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

       对于another requirement ，再开个数组，做动归，购买一种cookie可换得的满意度。

       由于group中的cookie 购买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;
}