#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 11;
const int Cash = 100001;
int res[Cash];
int cnt[Cash];
int num[N];
int val[N];

int get_res(int cash, int n)
{
	if(cash == 0 || n == 0)
		return 0;

	memset(res, 0, sizeof(res));
	for(int i=1; i<=n; i++)
	{
		memset(cnt, 0, sizeof(cnt));
		for(int j=1; j<=cash; j++)
		{
			if(j - val[i] >= 0 && cnt[j - val[i]] < num[i] && res[j] < res[j-val[i]] + val[i])
			{
				res[j] = res[j-val[i]] + val[i];
				cnt[j] = cnt[j-val[i]] + 1;
			}
		}
	}
	return res[cash];
}

int main()
{
	int n, cash;
	while(scanf("%d%d", &cash, & n) != EOF)
	{
		for(int i=1; i<=n; i++)
			scanf("%d%d", &num[i], &val[i]);
		int tmp = get_res(cash, n);
		printf("%d\n", tmp);
	}
	return 0;
}

• Re:转化为完全背包问题，背包九讲给力啊 (15) illuminator 2013-03-24 09:32:36
  • Re:转化为完全背包问题，背包九讲给力啊 (19) 2007011268 2013-04-21 10:30:34
    • Re:转化为完全背包问题，背包九讲给力啊 (12) 2007011268 2013-04-21 10:30:57
      • Re:转化为完全背包问题，背包九讲给力啊 (10) 2007011268 2013-04-21 10:31:13