#include <bits/stdc++.h>
using namespace std;

int n, a[20], dp[40000], sum[40000];

int popcount(int x)
{
	int cnt = 0;
	while (x)
	{
		x = x & (x - 1);
		cnt ++;
	}
	return cnt;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", &a[i]);
	}

	for (int i = 0; i < (1 << n); i ++)
	{
		int t = i;
		for (int j = 1; j <= n; j ++)
		{
			if (t % 2 == 1)
			{
				sum[i] += a[j];
			}
			t /= 2;
		}
	}
	
//	for (int i = 0; i < (1 << n); i ++)
//	{
//		cout << sum[i] << " ";
//	}
//	cout << endl;
	
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int k = 1; k <= n; k ++)
	{
		for (int i = 0; i < (1 << n); i ++)
		{
			if (popcount(i) == k - 1)
			{
				for (int j = 0; j < n; j ++)
				{
					if ((i >> j) % 2 == 0)
					{
						//cout << i << " " << dp[i] << " " << a[j + 1] << " " << sum[i] << endl;
						dp[i + (1 << j)] = min(dp[i + (1 << j)], dp[i] + max(0, a[j + 1] - sum[i] % 1000));
					}
				}
			}
		} 
	}
	cout << dp[(1 << n) - 1]; 
	return 0;
}

这是代码，不知为何，RE了

题面

有一家商店正在做促销，出售N个产品，第i个产品的标价为M[i]元。

促销内容为：每次购买都会获得“您迄今为止购买的商品的标价总和%100的折扣。

但是，如果您购买的商品折扣后价格低于 0元，则将以 0元购买。

你每个产品都需要 1个，可以按照任意顺序购买，每次只能买 1个产品。你想知道最少需要花多少元。