学步园

题目大意：给定一个数m,还有一组数，分别表示这个元素的个数num[i], 单个价值为value[i]。要你求最这组元素价值和最接近m的最大值

解题思路：多重背包问题，拆分2进制或单调队列

同poj 1014一样

http://blog.csdn.net/xiaoxiaoluo/article/details/7816378

2进制拆分方法：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100010;
const int maxm = 10010;
int dp[maxn];
int cash, n, index, nk[11], dk[11], value[maxm];

void spilt(int n, int v);
int main()
{
	
	while(scanf("%d %d", &cash, &n) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		index = 0;
		for(int i = 0; i < n; i++)
		{
			scanf("%d %d", &nk[i], &dk[i]);
			spilt(nk[i], dk[i]);
		}
		
		if(cash == 0)
		{
			printf("0\n");
			continue;
		}
		
		for(int i = 0; i < index; i++)
		{
			for(int j = cash; j >= value[i]; j--)
				dp[j] = max(dp[j], dp[j - value[i]] + value[i]);
		}
		printf("%d\n", dp[cash]);
	}
	
	return 0;
}

void spilt(int n, int v)
{
	int x, i = 0, tmp = 0;
	while(true)
	{
		x = 1 << i;
		if(tmp + x > n)
			break;
		tmp += x;
		value[index++] = x * v;
		i++; 
	}
	x = n - tmp;
	if(x > 0)
		value[index++] = x * v;
}

单调队列的方法：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node
{
	int index, value;
};

const int maxn = 100010;
const int maxm = 10010;
int dp[maxn];
int cash, n, nk[11], dk[11];
node que[maxn];

int main()
{
	
	while(scanf("%d %d", &cash, &n) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < n; i++)
			scanf("%d %d", &nk[i], &dk[i]);
		
		if(cash == 0)
		{
			printf("0\n");
			continue;
		}
		
		for(int i = 0; i < n; i++)
		{
			int t = nk[i] * dk[i];
			if(nk[i] == 1)
			{
				for(int j = cash; j >= dk[i]; j--)
					dp[j] = max(dp[j], dp[j - dk[i]] + dk[i]);
			}
			else if(t >= cash)
			{
				for(int j = dk[i]; j <= cash; j++)
					dp[j] = max(dp[j], dp[j - dk[i]] + dk[i]);
			}
			else
			{
				for(int j = 0; j < dk[i]; j++)
				{
					int head = 0, tail = -1;
					for(int k = j, nu = 0; k <= cash; k += dk[i], nu++)
					{
						if(head <= tail && k - que[head].index > t)
							head++;
						int tt = dp[k] - nu * dk[i];
						while(head <= tail && que[tail].value < tt)
							tail--;
						tail++;
						que[tail].index = k;
						que[tail].value = tt;
						
						dp[k] = que[head].value + nu * dk[i];
					}
				}
			}
		}
		printf("%d\n", dp[cash]);
	}
	
	return 0;
}