http://info.zjfc.edu.cn/acm/contest/contest_problemDetail.aspx?pid=1005&cid=32
題目描述：
    給定一個背包的容量k，給定n個物品的體積和價值，物品不可分割，將n個物品中選若干個物品放入背包，求背包內(nèi)物品的最大價值總和，在價值總和最大的前提下求背包內(nèi)的最小物品個數(shù)c。
輸出描述：
    第一行是一個整數(shù)t，表示測試數(shù)據(jù)的組數(shù)t。
    對于每組測試數(shù)據(jù)，第一行是兩個整數(shù)n和k,表示物品的個數(shù)和背包的容量；
    接下來n行，每行兩個整數(shù)，分別是物品的價值和體積。
輸出描述：
    輸出背包內(nèi)物品的最大價值v，在價值最大的前提下求背包內(nèi)的最小物品個數(shù)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;//最小物品數(shù)
    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;
}