Algo solution test(with reach334).cpp

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class TestData
{
public:
	int N;          // 箱子个数
	vector<int> m;  // 自重
	vector<int> M;  // 承重

	void print()
	{
		printf("N = %d\n", N);
		printf("m[] = ");
		for (int i = 0; i < N; ++i)
			printf("%d ", m[i]);
		putchar('\n');

		printf("M[] = ");
		for (int i = 0; i < N; ++i)
			printf("%d ", M[i]);
		putchar('\n');
	}
};

TestData genTestData()
{
	TestData data;
	int N = rand() % 1000;
	data.N = N;
	data.m.resize(N);
	data.M.resize(N);
	for (int i = 0; i < N; ++i) {
		data.m[i] = rand() % 3000;
		data.M[i] = rand() % 3000;
	}
	return data;
}

class MC
{
public:
	MC(const TestData &_data)
	{
		data = _data;
		f.resize(F_SIZE);
	}
	int solve()
	{
		for (int i = 0; i < F_SIZE; ++i) {
			f[i] = 0;
		}

		for (int i = 0; i < data.N; ++i) {
			for (int j = 0; j <= data.M[i]; ++j) {
				int pos = j + data.m[i];
				f[pos] = max(f[pos], f[j]+1);
			}
		}

		int maxima = 0;
		for (int i = 0; i < F_SIZE; ++i)
			maxima = max(maxima, f[i]);
		return maxima;
	}

	static const int F_SIZE = 6001;
	TestData data;
	vector<int> f;
};

class ME
{
public:
	ME(const TestData &_data)
	{
		data = _data;
	}

	int solve()
	{
		int maxima = 0;
		for (int i = 0; i < data.N; ++i) {
			maxima = max(maxima, recur(INT_MAX, i));
		}
		return maxima;
	}

private:
	int recur(int W, int i)
	{
		auto iter = f.find(pair<int, int>(W, i));
		if (iter != f.end())
			return iter->second;

		if (W < data.m[i]) {
			f.insert(make_pair(pair<int, int>(W, i), 0));
			return 0;
		}
			
		if (W == data.m[i] || (W >= data.m[i] && i == data.N-1)) {
			f.insert(make_pair(pair<int, int>(W, i), 1));
			return 1;
		}

		if (W > data.m[i]) {
			int next_W = min(data.M[i], W-data.m[i]);

			int maxima = 0;
			for (int k = i + 1; k < data.N; ++k) {
				int val = recur(next_W, k);
				maxima = max(maxima, val);
			}
			f.insert(make_pair(pair<int, int>(W, i), maxima+1));
			return maxima+1;
		}
		throw runtime_error("Impossible to reach here");
	}

	TestData data;
	map<pair<int, int>, int> f;
};


int main()
{
	TestData d1 = genTestData();
	d1.print();

	MC mc1(d1);
	printf("%d\n", mc1.solve());

	ME me1(d1);
	printf("%d\n", me1.solve());

	getchar();
	return 0;
}

My algo:

M[N] 承重
m[N] 自重

设通过某个策略，已经安放好了 0~i-1 的箱子(具体放置策略未知，有可能一个都不放，只要是合法的策略即可)；
设这个策略下，当前提供的最大承重为 W。
f(W, i) 为当前情况下，“一定放上箱子 i” 的策略最多能增加多少个箱子。

f(W, i) = 
    0     if  W < m[i]
          （放上 i 就超重）
    1     if  W = m[i] or (W >= m[i] and i=N-1) 
          （刚刚好放上 i，或者 “虽然还有承重空间但是 i 已经是最后一个箱子”）
    1 + max { f(min(W-m[i], M[i]), k ) }  (k = {i+1, i+2, ... N-1})    else

ans = max{ f(正无穷, k) }   (k = {0, 1, ... N-1})

MC reference impl:

int f[6001]
int m[1000]
int M[1000]

for i = 0 ~ 6000:
    f[i] = 0

for i = 0 ~ 999:
    for j = 0 ~ M[i]:
        f[j+m[i]] = max(f[j+m[i]], f[j] + 1)

int ans = 0
for i = 0 ~ 6000:
    ans = max(ans, f[i])

One test result:

N = 41
m[] = 467 2500 724 2358 464 1145 1827 491 2942 2436 2604 153 382 716 1895 726 2538 1912 2299 894 2811 333 1664 1711 868 644 2757 859 741 778 35 1842 106 2942 1648 2805 729 350 1101 548 623
M[] = 334 1169 2478 2962 2705 2281 961 2995 1827 2391 902 292 2421 1718 2447 2771 1869 1667 2035 1703 1322 2673 141 1253 1547 2662 2037 2723 529 316 1190 288 40 1264 446 890 370 6 393 1629 84
36
8

These 2 algo is not mathematical identical.

N个大小相同的纸箱，分别编号1～N，N取值范围[1, 1000]，每个纸箱的自重和承重能力各异，取值范围均为[1, 3000]，现在把这些纸箱按编号从小到大、一个一个地竖直堆叠起来（编号小的在下方，编号大的在上方，可以选择放置或者不放某个箱子），问最多可以堆叠多少个。