ACM校队暑假培训终于结束了，大家很兴奋，为此想一起聚餐庆祝一下。大家一共带了S money去了一家餐厅。这家餐厅共有m
道不同的菜可点。由于口味各不相同，所以定了个这么点菜规则：
每人点一道菜，且不能点相同的菜，直到所有人都点完或者所剩的钱不够去再点新的一道菜。现在就让你来计算一下最多可能的花费。



Input

输入多组测试数据，每组第一行为三个正整数，n，m，s分别代表这次晚餐总人数，餐厅可点的菜数，以及共带去的钱数。接下去
一行m个数，分别描述每道菜的价格，也都为正整数。n≤20 , m≤50 , s≤1000

Output

每个测试数据一行，本次聚餐可能的最高消费。

Sample Input


10 15 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 6 25
2 3 4 5 6 24


Sample Output


100
24

mark

[ 本帖最后由 voidx 于 2011-8-4 13:21 编辑 ]

看一下这个方法，输入输出的形式没按要求来...
#include<stdio.h>

void MaxMoney(int n,int m,int p[],int s)
{ int maxmoney=0;
  for(int i=0;i<n;i++)
  for(int i=0;i<m;i++)
  if(p[i]<=s)
  { maxmoney+=p[i];s=s-p[i];}
  printf("最高消费为：%d\n",maxmoney);
}

int main()
{
   int a;
   //printf("请输入测试数据的组数:");
   scanf("%d",&a);
   
   for(int i=0;i<a;i++)
   {    int n,m,s,i,h;
    int p[50];
  //printf("请输入人数n(小于等于20),菜数m(小于等于50),钱数s(小于等于1000):\n");
    scanf("%d %d %d",&n,&m,&s);
  //printf("请输入个菜价格：\n");
    for( i=0;i<m;i++) scanf("%d",&p[i]);
    for( i=0;i<m;i++)
    {  
        for(int j=i+1;j<m;j++)
        if(p[i]<p[j])
        {
            int q;
            q=p[j];
            p[j]=p[i];
            p[i]=q;
        }
    }
  MaxMoney(n,m,p,s);
}
  return 0;

}

先Mark 回去想想

老兄，这个只有三层循环得不出正确答案的。。。。。。。。。。。。。。。看看有没有其他方法啊

动态规划  总觉得是二维的 但是试了试貌似是线性的

但是得不出正确的结果  估计还是二维的

求那位高人能把状态转移方程求出

把价格从大到小排序，每个人都挑最贵的点（不重复），直到钱不够或用完，不就能算出可能的最高消费吗？
难道不行？

[ 本帖最后由 吴辉 于 2011-8-4 19:44 编辑 ]

背包问题，主要的方程如下，边界自己处理
f[i][j][k] = max{ f[i-cost[j]][j-1][k-1], f[i][j-1][k] }

滚动数组可优化空间

不行，这样只能求出普通情况，可能后面两个数加起来比你前面一个数加上后面一个小数大，但是你要选前面两个大数的话会超过范围，比如说x , y , z ,t, h ,l ，x+y超界，所以你可能只能选x+l但是可能t+h比你x+l大，所以从大到小排并不能确保最大

求大神详解~