Skip to content

Instantly share code, notes, and snippets.

@zsh-89

zsh-89/Algo solution test(with reach334).cpp

Created March 20, 2016 12:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save zsh-89/93b80e0a4e229a998ab2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save zsh-89/93b80e0a4e229a998ab2 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
@zsh-89
Copy link
Author

zsh-89 commented Mar 20, 2016

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.

@zsh-89
Copy link
Author

zsh-89 commented Mar 20, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment