1001

AC代码

#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

bool cmp(int a, int b){
    return a>b?1:0;
}
int main(){
  int n,m,s;
    while( cin >> n >> m >> s){
        int val[60];
        for(int i=0; i<m; ++i ){
            cin >> val[i];
        }
        sort(val,val+m,cmp);
        int dp[1009]={1};
        for(int i=0; i<m; ++i){
            for(int j=s; j>=val[i]; --j){
                if(dp[j-val[i]]){
                    if(!dp[j] && j==val[i])
                        dp[j]=dp[j-val[i]];
                    else if(!dp[j] || dp[j] > dp[j-val[i]]+1)
                        dp[j]=dp[j-val[i]]+1;

                }
            }
        }
        for(int i=s; i>=0; --i)
            if(dp[i] && dp[i]<=n ){
                 cout << i << endl;
                break;
            }
    }
  return 0;
}

如果点24的菜，才一道菜啊，最少要两个菜啊
24+2=26>25，不成立啊

#include<stdio.h>
#define n 20
#define m 50
//#define s 2000
void knap_bag(int *c,int *w)
{
    int f[n+1][m+1];//i+1件物品，m为容量
    int i,j;
    //int s;
    for(i=0;i<=n;i++)//初始化
    {
        for(j=0;j<=m;j++)
        {
            f[i][j]=0;
        }
    }
    //f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+w[i]}
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(c[i]<=j)
            {
                if(f[i-1][j-c[i]]+w[i]>f[i-1][j])
                {
                    f[i][j]=f[i-1][j-c[i]]+w[i];//选择该菜
                }
                else
                    f[i][j]=f[i-1][j];//不选择该菜
            }
            else
                f[i][j]=f[i-1][j];//容量不足
        }
    }
    printf("最优解：\n");
 //    if(f[n][m]<=s)
    printf("%d\n",f[n][m]);
    //由那个菜组成
    int temp_wei=m;
    int x[n+1]={0,0,0,0};
    for(i=n;i>0;i--)
    {
        if(f[i][temp_wei]==f[i-1][temp_wei])//最后选择的物品一定是最大的
        {
            x[i]=0;
        }
        else
        {
            x[i]=1;
            temp_wei=c[i];
        }
    }
    printf("应点的菜为：");
    for(i=0;i<=n;i++)
    {
        if(x[i])
        {
            printf("第 %d 件",i);
        }
    }
    printf("\n");
}
int main()
{
    //int s=25;
    int c[6]={2 3 4 5 6 24};//物品质量
    int w[6]={0,6,3,4,5,4}; //物品价值
    return 0;
}

收到的鲜花

• 好孩子好宝贝 于 2011-08-18 13:56 送鲜花  1朵  

他没说每个人都必须点一道菜 有些人不点也是可以的

所以这题就是在满足点菜个数不超过人数且价格不能多于所带钱的的前提下的最大值

这道题的文字叙述和后面举例都不是一回事。文字叙述并无规定所有菜的价格都不一样，但举例和解题都隐藏了这个潜规则，明显与题意不符。假定这个规则是符合题意的，那么实际上不会有这样的餐厅，找出这种算法对实际应用没有帮助。

这个是背包问题的一种，跟 0-1 背包问题有点相似，找了本背包问题的书，不过还没看，如果我看明白了一定尽力写个小程序出来~

谁能写出他的ＡＣ代码啊？？？？？

我不是写出了么

#include<stdio.h>
int main()
{
    int n,m,s;
    while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    {
        int i,o,a[50],price=0;
        for(i=0;i<m;i++)
            scanf("%d",&a[i]);
        for(i=m-1,o=0;i>=0;i--)
        {
            if(o<n&&(price+a[i])<=s)
            {
                o=o+1;
                price=price+a[i];
            }
        }
        printf("Max=%d\n",price);
    }
    return 0;
}
不知道是不是这个？