13?? why。。。。
#include<iostream>
using namespace std;
struct Point
{
    char Name[50];
    int Price,Value;
}P[101];
int N,M;
unsigned long long Ans=(unsigned long long)1<<63;
long long DP[40010];
int Num[40010];
int Pre[40010];
int Sel[40010];
int Hash[101];
int main()
{
    scanf("%d%d\n",&N,&M);
    M=M*1000;
    for(int i=1;i<=N;i++)
    {
        double Tmp;
        scanf("%s %d %lf",&P[i].Name,&P[i].Price,&Tmp);
        P[i].Value=int(Tmp*1000+0.0001);
    }
    DP[0]=1;
    for(int i=1;i<=N;i++)
        for(int j=0;j<=M;j++)
            if(DP[j])
            {
                if(DP[j+P[i].Value]==0)
                {
                    DP[j+P[i].Value]=DP[j]+P[i].Price;
                    Pre[j+P[i].Value]=j;
                    Sel[j+P[i].Value]=i;
                    if(i==Sel[j]) Num[j+P[i].Value]=Num[j];
                    else Num[j+P[i].Value]=Num[j]+1;
                }
                else if(DP[j+P[i].Value]>DP[j]+P[i].Price)
                {
                    DP[j+P[i].Value]=DP[j]+P[i].Price;
                    Pre[j+P[i].Value]=j;
                    Sel[j+P[i].Value]=i;
                    if(i==Sel[j]) Num[j+P[i].Value]=Num[j];
                    else Num[j+P[i].Value]=Num[j]+1;
                }
                else if(DP[j+P[i].Value]==DP[j]+P[i].Price)
                {
                    if(i==Sel[j])
                    {
                        if(Num[j+P[i].Value]<Num[j])
                        {
                            Pre[j+P[i].Value]=j;
                            Sel[j+P[i].Value]=i;
                            Num[j+P[i].Value]=Num[j];
                        }
                    }
                    else
                    if(Num[j+P[i].Value]<=Num[j]+1)
                    {
                        Pre[j+P[i].Value]=j;
                        Sel[j+P[i].Value]=i;
                        Num[j+P[i].Value]=Num[j]+1;
                    }
                }
            }
    int TT;
    for(int i=M;i<=M+20000;i++)
        if(DP[i]&&DP[i]<Ans) Ans=DP[i],TT=i;
        else if(DP[i]&&DP[i]==Ans&&Num[i]>Num[TT]) Ans=DP[i],TT=i;
    cout<<Ans-1<<endl;
    while(TT>=1)
    {
        Hash[Sel[TT]]++;
        TT=Pre[TT];
    }
    for(int i=1;i<=N;i++)
        if(Hash[i])
            printf("%s %d\n",P[i].Name,Hash[i]);
    return 0;
}

Edited by author 10.03.2010 13:51