http://info.zjfc.edu.cn/acm/contest/contest_problemDetail.aspx?pid=1005&cid=32
题目描述：
    给定一个背包的容量k，给定n个物品的体积和价值，物品不可分割，将n个物品中选若干个物品放入背包，求背包内物品的最大价值总和，在价值总和最大的前提下求背包内的最小物品个数c。
输出描述：
    第一行是一个整数t，表示测试数据的组数t。
    对于每组测试数据，第一行是两个整数n和k,表示物品的个数和背包的容量；
    接下来n行，每行两个整数，分别是物品的价值和体积。
输出描述：
    输出背包内物品的最大价值v，在价值最大的前提下求背包内的最小物品个数c，中间用一个空格隔开。
样例输入：
1
3 10
4 5
6 5
10 10
样例输出：
10 1
作者：
xiewenxiu
//16829 2009-05-08 19:58:40 1005  Accepted 765MS 464K Visual C++ liyunsong 
#include<iostream>
using namespace std;
struct Node
{
    int ns;//最小物品数
    int vs;//最大价值
}dp[2001];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int v[2001],w[2001];
        int n,c;
        int i,j;
        cin>>n>>c;
        for(i=1;i<=n;i++)
            scanf("%d%d",&v[i],&w[i]);
        for(j=0 ; j < w[1];j++)
        {
            dp[j].vs = 0;
            dp[j].ns = 0;
        }
        for(; j <= c;j++)
        {
            dp[j].vs = v[1];
            dp[j].ns = 1;
        }
        for(i=2;i<=n;i++)
        {
            for(j=c;j>=w[i];j--)
            {
                if(dp[j].vs < dp[j-w[i]].vs + v[i])
                {
                    dp[j].vs = dp[j-w[i]].vs + v[i];
                    dp[j].ns = dp[j-w[i]].ns + 1;
                }
                else if(dp[j].vs == dp[j-w[i]].vs + v[i] && dp[j].ns > dp[j-w[i]].ns + 1)
                    dp[j].ns = dp[j-w[i]].ns + 1;
            }
        }
        cout<<dp[c].vs<<" "<<dp[c].ns<<endl;
    }
    return 0;
}