【ACM】采购

周末，小明要去超市采购。超市备货充足，每种商品的数量都足够。他需要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个整数，用空格分隔，表示每种商品的购买数量。如果方案不唯一，输出最靠左的。

### 输入样例:

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

```in
3 10
4 5 6
3 4 5
```

### 输出样例:

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

```out
13
2 1 0
```

### 当时我写的

```c
#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.

最后修改：2023 年 07 月 25 日