周末,小明要去超市采购。超市备货充足,每种商品的数量都足够。他需要n种商品,赋予每种商品一个权值,表示需要该商品的程度,权值越大,就越需要该商品。他的预算是M元,如何选择商品,才能最大程度满足他的需要。

输入格式:

第1行,两个整数n和M,分别代表商品数和预算,1≤n≤1000,0≤M≤400。

第2行,n个整数Di,用空格分隔,表示第i个商品的需要度,1≤i≤n,1≤Di≤100.

第3行,n个整数Pi,用空格分隔,表示第i个商品的价格,1≤i≤n,1≤Pi≤100.

输出格式:

第1行,1个整数,表示能得到的需要的最大程度。

第2行,n个整数,用空格分隔,表示每种商品的购买数量。如果方案不唯一,输出最靠左的。

输入样例:

在这里给出一组输入。例如:

3 10
4 5 6
3 4 5

输出样例:

在这里给出相应的输出。例如:

13
2 1 0

当时我写的

#include<stdio.h>

int n,M,count1,max1,min1;
int p[1001][2];
int a[1001],b[1001];

void Fivk(int x)
{
    int i;
    if(x<min1)
    {
        if(count1>max1)
        {
            max1=count1;
            for(i=0;i<n;i++)
            {
                b[i]=a[i];
            }
        }
    }else{
        for(i=0;i<n;i++)
        {
            if(x>=p[i][1])
            {
                x-=p[i][1];
                count1+=p[i][0];
                a[i]++;
                Fivk(x);
                a[i]--;
                count1-=p[i][0];
                x+=p[i][1];
            }
        }
    }
}

int main()
{
    scanf("%d %d",&n,&M);
    min1=100;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i][0]);
    }

    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i][1]);
        if(p[i][1]<min1) min1=p[i][1];
    }
    Fivk(M);

    printf("%d\n",max1);
    for(int i=0;i<n;i++)
    {
        printf("%d",b[i]);
        if(i<n-1) printf(" ");
    }
    printf("\n");
    return 0;
}

超时了,能否来个大佬教教我qvq.

最后修改:2021 年 05 月 19 日
如果觉得我的文章对你有用,请随意赞赏