TOJ 3290

タイトル:
Watch The Movie
テーマ接続:
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3290
テーマのタイプ:
ダイナミック企画-多次元リュックサック
データ構造:

struct LMIC_MOVIE
{
	int t, v;
};

//   ,     
int dp[1005][1005];

考え方の分析:
リュックサックの問題、
制限条件は2つあります。
一つは時間Lで、どの映画にもその時間があります。合計はLを超えてはいけません。
一つは数量Mで、一つの映画は数量1のものに相当します。合計はMを超えてはいけません。
単純な01バックパックを利用して1次元を多く入れる方法。
多次元のリュックサックが実現できます。
証明:
省略する
ソースコード:

#include 
#include 
#include 
using namespace std;

struct LMIC_MOVIE
{
	int t, v;
};

//   ,     
int dp[1005][1005];


int main()
{
	int i, j, k, t, n, m, l;
	LMIC_MOVIE mie[105];
	
	scanf( "%d", &t );
	
	while( t -- )
	{
		scanf( "%d%d%d", &n, &m, &l );
		
		for (i = 0; i <= l; i ++ )
		{
			for (j = 0; j <= m; j ++ )
			{
				if( j )
				{
					dp[i][j] = -999999;
				}
				else
				{
					dp[i][j] = 0;
				}
			}
		}
		
		for( i = 1; i <= n; i ++ )
		{
			scanf( "%d%d", &mie[i].t, &mie[i].v );
		}
		
		for( i = 1; i <= n; i ++ )
		{
			for( j = l; j >= mie[i].t; j -- )
			{
				for( k = m; k >= 1; k -- )
				{
					if( dp[j][k] < dp[j - mie[i].t][k - 1] + mie[i].v )
					{
						dp[j][k] = dp[j - mie[i].t][k - 1] + mie[i].v;
					}
				}
			}
		}
		
		printf( "%d
", dp[l][m] >= 0 ? dp[l][m] : 0 );
	}
	
	return 0;
}