有点不同的完全背包问题  但思路还是一样的

/*************************************************************************

    > Author: xlc2845       > Mail: xlc2845@gmail.com

    > Created Time: 2013年10月22日 星期二 13时04分26秒

 ************************************************************************/

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <iostream>

#include <string>

#include <vector>

#include <map>

#include <cmath>

#define MAX 0x7fffffff

#define maxn 310

using namespace std;

int dp[maxn][maxn],w1,w2;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m,ans = MAX;

        scanf("%d%d",&n,&m);

		for(int i = 0; i <= m; i++)

			for(int j = 0; j <= m; j++)

				dp[i][j] = MAX;

		dp[0][0] = 0;

        for(int i = 0; i < n; i++)

		{

            scanf("%d%d",&w1, &w2);

            for(int j = w1; j <= m; j++)

                for(int k = w2; k <= m; k++)

                {

                    int nx = j-w1, ny = k-w2;

                    if(dp[nx][ny] != MAX)

                    {

                        dp[j][k] = min(dp[j][k], dp[nx][ny]+1);

                        if(k*k+j*j == m*m)

                            ans = min(ans, dp[j][k]);

                    }

                }

		}

        if(ans != MAX)

			printf("%d\n",ans);

        else

			puts("not possible");

    }

    return 0;

}