#include <iostream>

int cash;            
int N;                 //货币种数
int num[11];           //每种货币数量数组
int value[11];         //每种货币价值
int f[100001];         //动态规划数组
#define Max(a,b) (a)>(b)?(a):(b)

void ZeroOnePack(int cost, int weight)
{
	for (int i = cash; i >= cost; i--)
	{
		f[i] = Max(f[i], f[i - cost] + weight);
	}
}

void CompletePack(int cost, int weight)
{
	for (int i = cost; i <= cash; i++)
	{
		f[i] = Max(f[i], f[i - cost] + weight);
	}
}

int main(void)
{
	while (std::cin >> cash >> N)
	{
		for (int i = 0; i < N; i++)
		{
			std::cin >> num[i];
			std::cin >> value[i];
		}
		memset(f, 0, sizeof(f));
		for (int i = 0; i < N; i++)
		{
			if (num[i] * value[i] > cash)
			{
				CompletePack(value[i], value[i]);
			}
			else
			{
				int k = 1;
				int amount = num[i];
				while (k < amount)
				{
					ZeroOnePack(value[i], value[i]);
					amount -= k;
					k *= 2;
				}
				ZeroOnePack(amount * value[i], amount * value[i]);
			}
		}
		std::cout << f[cash] << std::endl;
	}
	return 0;
}

• Re:求大神帮助，这段代码为什么WA！！！！ (1189) 1131250907 2015-04-27 21:13:22
• Re:求大神帮助，这段代码为什么WA！！！！ (1189) 15605563213 2019-12-08 16:56:41
• Re:求大神帮助，这段代码为什么WA！！！！ (1189) 20192660 2021-05-16 01:04:08