zoj 1558 背包 博客分类： acm c++acm

#include <bits/stdc++.h>
using namespace std;
int num[8],dp[10000+10];
int cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=1;i<7;i++)
            scanf("%d",&num[i]);
        sort(num+1,num+7,cmp);
         int sum = num[1]*100+100;
        //memset(dp,0,sizeof(dp));
        for(int i=1;i<=sum;i++)
            dp[i]=i;
        for(int k=1;k<=6;k++)
        {
            for(int j=num[k];j<=sum;j++)
            {
               if(dp[j]>dp[j-num[k]]+1)
                dp[j] = dp[j-num[k]]+1;
            }
        }
        for(int k=1;k<=6;k++)
        {
            for(int j=sum-num[k];j>=0;j--)
            {
                dp[j] = min(dp[j+num[k]]+1,dp[j]);
            }
        }
        sum = 0;int maxx = 1;
        for(int i=1;i<=100;i++)
        {
            sum+=dp[i];
            maxx = max(maxx,dp[i]);
        }
        printf("%d.%d %d\n",sum/100,sum%100,maxx);
    }
    return 0;
}