杭电 hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

首先对汶川大地震表示默哀.

进入正题:

代码中注释什么的,都已经很明确了,请直接看代码,当然第一个我没有什么注释,不过可以通过第二个明白第一个

// version 1 用时 > O( ∑n[i]*V ) 
/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   : http://poj.org/problem?id=2243
        Name  : Knight Moves

        Date  : Tuesday, April 20, 2010
        Time Stage : 0:14

        Result:
3857850 2011-04-23 06:47:26 Accepted 2191 15MS 284K 1277 B C++ pyy

Test Data:

Sample Input:
1
8 2
2 100 4
4 300 2

1
8 2
2 100 4
4 100 2

Sample Output:
600
400

//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#define debug 1
using namespace std;

const int maxSize = 200;
int maxWeight, money, kind;
int price[maxSize], num[maxSize], weight[maxSize];
int dp[maxSize];
void multipleBag()
{
	int i, j, k, used, prv_used;
	memset( dp, 0, sizeof( dp ) );
	for( i = 1; i <= kind; i++ )
	{
		for( j = 1; j <= num[i]; j++ )
		{
			for( k = money; k >= price[i]; --k )
				dp[k] = max( dp[k], dp[k-price[i]] + weight[i] );
		}
	}
	maxWeight = dp[money];
}

int main()
{
	int i, j, k, tcase;
	while( cin >> tcase )
	{
		while( tcase-- )
		{
			cin >> money >> kind;
			for( i = 1; i <= kind; i++ )
				cin >> price[i] >> weight[i] >> num[i];
			multipleBag();
			cout << maxWeight << endl;
		}
	}
	return 0;
}

// version 2 用时 > O( log amount )
/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   : http://poj.org/problem?id=2243
        Name  : Knight Moves

        Date  : Tuesday, April 20, 2010
        Time Stage : 3 hours around

        Result:
3858065 2011-04-23 09:30:16 Accepted 2191 15MS 284K 2954 B C++ pyy 

Test Data:

Sample Input:
1
8 2
2 100 4
4 300 2

1
8 2
2 100 4
4 100 2

Sample Output:
600
400

Review:
    此题为多重背包问题，详细理解请参考著名的<< 背包九讲>>.
    用<< 背包九讲>> 中O( log amount )时间处理一件物品的方法.个人感觉, 实际上就
是对多重背包进行分类处理:
    1.  如果一件物品在( 数量* 单价>= 可支配金额) 的情况下, 这件物品的使用就
可以认为是无限的, 也即可以用完全背包的形式进行处理. 
    2.  如果一件物品不属于上述情况, 也就是说可支配金额可以把这种物品买光, 就
应该使用01背包的形式进行处理.

    对于背包类的问题, 有几点需要注意的( 在代码中会有"注意:" 标识).
    1.  状态转移方程:
                dp[i] = max( dp[i], dp[i - p] + w ) 
        中max 函数的第一个参数:
                dp[i]
        究竟是dp[i] 好还是dp[i-1] 好?

    2. 
                for( j = 1; j < remainder; j *= 2 )
        中究竟是用remainder 还是num[i] ? 已知用num[i] 会出现
                   Runtime Error
                (ACCESS_VIOLATION)
        的错误. 即remainder 有可能会出现负数.
    3.  ( 看代码注释)
    4. 二进制的思想很强大, 请仔细深入理解注意中处理的思想和过程.
//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#define debug 0
using namespace std;

const int maxSize = 200;
int maxWeight, money, kind;
int price[maxSize], num[maxSize], weight[maxSize];
int dp[maxSize];

void completePack( const int & p, const int & w )
{
        #if debug
        printf( "-CompletePack : /n" );
        #endif
        int i, j, k;
        for( i = p; i <= money; i++ )
        {
                #if debug
                printf("dp[%d] : %d/t", i, dp[i] );
                #endif
                dp[i] = max( dp[i], dp[i - p] + w );    // 注意1
                #if debug
                printf("dp[%d] : %d/n", i, dp[i] );
                #endif
        }
        #if debug
        printf( "-End Of CompletePack. /n" );
        #endif
}

void zeroOnePack( const int & p, const int & w )
{
        int i, j, k;
        #if debug
        printf( "=zeroOnePack : /n" );
        #endif
        /*------------------------------ 注意3 --------------------------------//
        从最高费用开始处理可以避免同一个物品被多次使用的情况
        例如: dp[n-p] 和dp[n] ( p <= n <= money ) 都要使用到物品A, 如果是
        从i = p 开始, 则dp[n - p] 会先包含一个物品A, 到dp[n] 的时候, 会因为
        dp[n] = max( dp[n], dp[n - p] + w ) 的缘故, 再次把物品A 包含进来. 而这样
        将违反01背包一个物品只能使用一次的约定
        //----------------------------------------------------------------------*/
        for( i = money; i >= p; --i )                   
        {
                #if debug
                printf( "dp[%d] : %d/t", i, dp[i] );
                #endif
                dp[i] = max( dp[i], dp[i - p] + w );    // 注意1
                #if debug
                printf( "dp[%d] : %d/n", i, dp[i] );
                #endif
        }
        #if debug
        printf( "=End Of zeroOnePack : /n" );
        #endif
}

void multipleBag()
{
	int i, j, k, remainder;
	memset( dp, 0, sizeof( dp ) );
	for( i = 1; i <= kind; i++ )
	{
	        #if debug
	        printf( "Circle %d/n", i );
	        #endif
		if( num[i] * price[i] >= money )
                        completePack( price[i], weight[i] );
                else
                {
                        remainder = num[i];                     // 注意2
                        for( j = 1; j < remainder; j *= 2 )     // 注意2
                        {
                                zeroOnePack( j * price[i], j * weight[i] );
                                remainder -= j;
                        }
                                                                // 注意2
                        zeroOnePack( remainder * price[i], remainder * weight[i] );
                }
	}
	maxWeight = dp[money];
}

int main()
{
	int i, j, k, tcase;
	while( cin >> tcase )
	{
		while( tcase-- )
		{
			cin >> money >> kind;
			for( i = 1; i <= kind; i++ )
                                cin >> price[i] >> weight[i] >> num[i];
			multipleBag();
			cout << maxWeight << endl;
		}
	}
	return 0;
}