Description

农大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

http://acm.fafu.

  我师傅每次出手总是总结的太精辟了


   。。。。

此题和你的人民币问题差不多 只不过你的各种面值人民币不只一张

而这个每道菜只有一个（每人点一道菜，且不能点相同的菜）

所以只是维护散列表时用一重循环还是二重循环问题

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int n,m,s,i,j;
    while( cin >> n >> m >> s)
    {
        int val[60];
        for(i=0; i<m; ++i )
        {
            cin >> val[i];
        }
        int dp[1005]={1};
        for(i = 0;i<m;i++)
        {
            for(j = s;j>=val[i];--j)
            {
                if(dp[j-val[i]])
                {
                    if(!dp[j] && j == val[i])
                        dp[j] = 1;
                    else if(!dp[j] || dp[j]>dp[j-val[i]]+1)
                        dp[j] = dp[j-val[i]]+1;
                }
            }
        }
        for(i = s;i>=0;i--)
        {
            if(dp[i] && dp[i]<=n)
            {
                printf("%d\n",i);
                break;
            }
        }
    }
  return 0;
}

楼上各位大侠的程序看得我头痛......小弟寡闻了....

    我这里有一个自己以前编的背包算法的程序，大家看下：

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"

void Select_sort(int n,float *w, float *v,float *p)
{
    int i,l,j;
    float temp;
    for(i=1; i<=n-1; i++)
    {
        l=i;
        for(j=i+1; j<=n; j++)
            if(p[j]>p[l]) l=j;
        if(l!=i)
        {
            temp=p[l];
            p[l]=p[i];
            p[i]=temp;
           
            temp=w[l];
            w[l]=w[i];
            w[i]=temp;

            temp=v[l];
            v[l]=v[i];
            v[i]=temp;
        }
    }
}

void Knapsack(int n, float *v, float *w, float *x)
{
    int i;
    float *p;
    p=(float*)calloc(n+1,sizeof(float));
    for(i=1;i<=n;i++)
        p[i]=v[i]/w[i];
    Select_sort(n,w,v,p);
    for(i=1; i<=n; i++) x[i]=0;
    float c=500.0;
    for(i=1; i<=n; i++)
    {
        if(w[i]>c) break;
        x[i]=1;
        c-=w[i];
    }
    if(i<=n) x[i]=c/w[i];
}

void main()
{
    int i,n;
    float *w,*v,*p;
    float *x;
    float s=0.0;
    char flag='Y';
    srand(time(0));
    n=rand()%20+10;
    w=(float *)calloc(n+1,sizeof(float));
    v=(float *)calloc(n+1,sizeof(float));
    p=(float *)calloc(n+1,sizeof(float));
    x=(float *)calloc(n+1,sizeof(float));
    printf("产生的%d随即物品为:\n",n);
    while(flag='Y')
    {
        for(i=1; i<=n; i++)
        {
            int t1=rand()%100;
            float t2=t1/100.0;
            int t3=rand()%90+10;
            w[i]=(float)t3+t2;
            t1=rand()%100;
            t2=t1/100.0;
            t3=rand()%90+10;
            v[i]=(float)t3+t2;
            p[i]=v[i]/w[i];
        }
        Select_sort(n,w,v,p);
        for(i=1; i<=n; i++)
        {
            printf("物品%d的重量为:\n",i);
            printf("%4.2f\n",w[i]);
            printf("物品%d的价钱为:\n",i);
            printf("%4.2f\n",v[i]);
            printf("物品%d的单位价格为:\n",i);
            printf("%4.2f\n\n",p[i]);
        }
        Knapsack(n,v,w,x);
        printf("被选择的物品有:\n");
        for(i=1; i<=n; i++)
        {
            if(x[i]>0)
            printf("物品%d:重量为%4.2f,价格为%4.2f\n",i,x[i]*w[i],x[i]*v[i]);
        }
        for(i=1; i<=n; i++)
        {
            if(x[i]>0)
            s+=x[i]*v[i];
        }
        printf("\n");
        printf("最优值为:%4.2f\n",s);
        printf("是否继续背包问题算法?如果继续按Y,否则按N\n");
        getchar();
        scanf("%c",&flag);
        getchar();
        if(flag=='Y')
            continue;
        else break;
    }
}

真的越弄越不懂了，有些函数重来都没看到过，你写的，我收下了 以后在看看~~谢啦

#include <stdio.h>
int main()
{   
    int i,j;
    int n,m,s;
    while(EOF != scanf("%d%d%d",&n,&m,&s))
    {
        int dp[1001] = {0};
        for(i = 1;i<=s;i++)
            dp[i] = 0x7fffffff;
        int val;
        for(i = 0;i<m;i++)
        {
            scanf("%d",&val);
            for(j = s;j>0;j--)
                if(j>=val && (0 == j-val || dp[j-val]<0x7fffffff))
                    if(dp[j]>dp[j-val]+1)
                        dp[j] = dp[j-val]+1;
        }
        for(j = s;j>=0;j--)
            if(dp[j]<=n)
            {
                printf("%d\n",j);
                break;
            }
    }
    return 0;
}

刚刚把聚餐的题目优化了一下啊  应该先把dp数组设置为无穷大 然后再去dp这样可以省去很多判断