Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求大神帮助,这段代码为什么WA!!!!

Posted by liuxing12409 at 2014-05-21 23:55:10 on Problem 1276
#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;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator