杭電hdc 2159 FATE 2次元リュックサック

この問題は2次元のリュックサックの問題で、できないのはまず《リュックサック九講》(私も見ていませんが、やはり見る価値があります)、ここでもう1つ言って、アルゴリズムを学ぶのは例題を持って実践したほうがいいですが、実践は大量のテストデータがあるほうがいいです.
テストデータをクリアすることで、自分の誤りを明確に見つけることができ、アルゴリズムの処理過程を明確に理解することができます.各OJサイトが手を上げて、USCAOGのようにバックグラウンドのテストデータを見せて、間違いの中で死んでしまったacmerたちが迷子になるのを助けてほしい.

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2159
Name  : 2159 FATE

Date  : Saturday, August, 06, 2011
Time Stage :6 hours around

Result:

4348182	2011-08-06 16:27:14	Accepted	2159
15MS	228K	1399 B
C++	pyy



Test Data:

Review:
//----------------------------------------------------------------------------*/


#include <stdio.h>
#include <string.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define MAXSIZE 101

int need, remain, kind, kill ;
int val[MAXSIZE], cost[MAXSIZE], dp[MAXSIZE][MAXSIZE] ;

int twoDimension ()
{
	int i, j, k ;
	memset (dp, 0, sizeof (dp)) ;

	for (i = 1 ; i <= kind ; ++i)
	{
		for (j = 1 ; j <= kill ; ++j)
		{
			for (k = cost[i] ; k <= remain ; ++k)
			{
				dp[j][k] = max (dp[j][k], dp[j-1][k-cost[i]] + val[i]) ;
			}
		}
	}

	//          1.....kill    ，                 
	//      need   ，     。
	//          ，             
	for (i = 1 ; i <= remain ; ++i)
	{
		//		printf ("%d,%d ", dp[kill][i], i) ;
		if (dp[kill][i] >= need)
			break ;
	}
	//	puts ("") ;
	if (i > remain)
		return -1 ;
	return remain - i ;
}

int main ()
{
	int i, j ;
	while (scanf ("%d%d%d%d", &need, &remain, &kind, &kill) != EOF)
	{
		for (i = 1 ; i <= kind ; ++i)
		{
			scanf ("%d%d", &val[i], &cost[i]) ;
		}
		printf ("%d
", twoDimension ()) ;
	}
	return 0 ;
}