如果理解成 价值就是重量，转换成背包问题是ok的。

不过我按照“可达性”来理解做题，为什么就不对呢，代码很简单，请好心人帮看一下.

#include <stdio.h>
#include <memory.h>

#define MAX_CASH 100001
struct Cash
{
	int amount;
	int demo;
};

int dp[MAX_CASH];
int used[MAX_CASH];

Cash allCash[11];
int nCash;
int nDeliver;

int maxCash()
{
	if(nCash == 0 || nDeliver == 0)
		return 0;
	int i,j,k;
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;

	for( i = 1; i <= nCash; i++)
	{
		memset(used, 0, sizeof(used));

		for( j = allCash[i].demo ; j <= nDeliver; j++)
		{
			if(dp[j - allCash[i].demo] && 
 			   used[j - allCash[i].demo] < allCash[i].amount)
			{
				dp[j] = 1;
				used[j] = used[j-allCash[i].demo] + 1;
			} 
		}
	}
	
	for( i = nDeliver; i >= 0; i--)
	{
		if(dp[i])
		{
			return i;
		}
	}
	return 0;

}

int main()
{
	while(scanf("%d", &nDeliver) != EOF)
	{
		scanf("%d", &nCash);
		for( int i = 1; i <= nCash; i++)
		{
			scanf("%d%d", &allCash[i].amount, &allCash[i].demo);
		}
		printf("%d\n", maxCash());
	}
	return 0;
}

• Re:为什么这样理解就不对呢(测试数据都无恙的过了） (1169) 809959548 2012-08-14 14:43:54
• 同样想法，A了 (1081) ltf1320 2012-09-19 16:25:11