meal card HDU2546

meal card - HDU 2546 - Virtual Judge (csgrandeur.cn)

There is a very strange design of the dining card in the canteen of the University of Electronic Science and technology , That is to judge the balance before purchasing . If you buy a product before , The remaining amount on the card is greater than or equal to 5 element , You can buy it successfully （ Even if the card balance is negative after purchase ）, Otherwise you can't buy （ Even if the amount is enough ）. So we all hope to minimize the balance on the card .
One day , There are in the canteen n Grow vegetables and sell , Each dish can be purchased once . Know the price of each dish and the balance on the card , Ask the minimum balance on the card .

Input
Multiple sets of data . For each set of data ：
The first line is a positive integer n, Indicates the number of dishes .n<=1000.
The second line includes n A positive integer , Indicates the price of each dish . Price does not exceed 50.
The third line contains a positive integer m, Represents the balance on the card .m<=1000.

n=0 Indicates the end of the data .

Output
For each group of input , Output one line , Contains an integer , Indicates the minimum possible balance on the card .

Input

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

output

-45
32

Ideas

If you change the title to , Meal card balance m, n A dish , Try to buy dishes with the greatest total value , Then it's standard 01 knapsack problem .

But here is the minimum balance of the meal card , And the cost of this question is equal to the value , When the total value is the largest, the balance is the smallest , Subtract the total value from the total balance .

But there is also pawn The balance is Greater than 5 when , You can stuff large items beyond the capacity of your backpack , Then the optimal solution must be this 5 Buy the most expensive dishes with RMB , So I used the balance first 5 block , Buy the biggest one , The rest of the money and then ask for the maximum value of the remaining dishes .

The capacity of the backpack cannot overflow when it is left , That is, the standard 01 knapsack problem , Calculate the maximum value and add the original largest dish when exporting .

Code

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e3 +10;
int f[N];
int w[N];
int n,m;
int main()
{
    
	while(cin >> n && n)
	{
    
		memset(f, 0, sizeof f);
		for(int i = 1; i <= n;i ++)
			cin >> w[i];
		sort(w + 1, w + 1 + n);
		cin >> m;
		if(m < 5)
		{
    
			cout << m <<endl;
			continue;
		}
		for(int i = 1; i < n; i++)
			for(int j = m - 5; j >= w[i]; j --)
				f[j] = max(f[j], f[j - w[i]] + w[i]);
		cout << m - a[n] - f[m - 5] << endl;
	}
	
	return 0;
}