l*********y
发帖数: 52 | 1 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
有的盒子
比如 7*7 5*5, 4*6, 3*3
答案是7*7+4*6
这个题目大家有没有什么好的解法，贪婪算法该怎么做呢？ 多谢啦！ |
z***m
发帖数: 1602 | 2 先按长的边sort，然后用求longest increasing subsequence |
c*****n
发帖数: 95 | |
G*****m
发帖数: 5395 | 4 貌似不保证optimal吧
【在 z***m 的大作中提到】
: 先按长的边sort，然后用求longest increasing subsequence
|
z***m
发帖数: 1602 | 5 我也只能想到这儿了
【在 G*****m 的大作中提到】
: 貌似不保证optimal吧
|
e***i
发帖数: 231 | 6 先按面积/length/width sort，然后dp？另外，相等的情况算可以套还是不可以？
似乎greedy不能保证length/width sort最优
9*9
2*8
3*6
【在 l*********y 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 比如 7*7 5*5, 4*6, 3*3
: 答案是7*7+4*6
: 这个题目大家有没有什么好的解法，贪婪算法该怎么做呢？ 多谢啦！
|
g*****y
发帖数: 1120 | 7 Dp貌似可以。recursive 最简单
【在 e***i 的大作中提到】
: 先按面积/length/width sort，然后dp？另外，相等的情况算可以套还是不可以？
: 似乎greedy不能保证length/width sort最优
: 9*9
: 2*8
: 3*6
|
T*****u
发帖数: 7103 | 8 把盒子们按照可套否存成一个从大到小，从左到右的graph，然后split成一维list，同
一个level上最大的子线路或者end node的数量决定了分支的多少， |
x*******9
发帖数: 138 | 9 SPOJ MDOLLS
4A（有点蠢
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
int n;
vector > vec;
int main() {
int T;
int a, b;
input(T);
while (T--) {
input(n);
vec.clear();
multiset st;
for (int i = 0; i < n; i++) {
input(a >> b);
vec.push_back({a, b});
}
sort(vec.begin(), vec.end(),
[](const pair& pa, const pair& pb)->bool {
if (pa.first != pb.first) {
return pa.first < pb.first;
} else {
return pa.second > pb.second;
}
});
for (auto& p: vec) {
int u = p.second;
if (st.empty()) {
st.insert(u);
continue;
}
auto iter = st.lower_bound(u);
if (iter == st.begin()) {
st.insert(u);
} else {
--iter;
st.erase(iter);
st.insert(u);
}
}
print(st.size());
}
return 0;
} |
j********g
发帖数: 5 | 10
Create a graph: node is (length, width), there is an directed edge between
v1, v2 if v1 can be fit in v2. Topological sort the graph, and obtain a
topological sort array. From the array, find out the results.
【在 l*********y 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 比如 7*7 5*5, 4*6, 3*3
: 答案是7*7+4*6
: 这个题目大家有没有什么好的解法，贪婪算法该怎么做呢？ 多谢啦！
|
|
|
T*****u
发帖数: 7103 | 11 牛！
【在 j********g 的大作中提到】
:
: Create a graph: node is (length, width), there is an directed edge between
: v1, v2 if v1 can be fit in v2. Topological sort the graph, and obtain a
: topological sort array. From the array, find out the results.
|
z****8
发帖数: 5023 | |
a******7
发帖数: 106 | 13 这个建图就n平方了吧
【在 j********g 的大作中提到】
:
: Create a graph: node is (length, width), there is an directed edge between
: v1, v2 if v1 can be fit in v2. Topological sort the graph, and obtain a
: topological sort array. From the array, find out the results.
|
r******j
发帖数: 92 | 14 9*9套3*6
2*8
greedy可以啊 总是套下一个能套进去的面积最大的 为什么不可以？
【在 e***i 的大作中提到】
: 先按面积/length/width sort，然后dp？另外，相等的情况算可以套还是不可以？
: 似乎greedy不能保证length/width sort最优
: 9*9
: 2*8
: 3*6
|
c*******e
发帖数: 373 | 15 6x5
7x4
6x3
4x4
这个例子，贪婪法会失败
因为 6x5的套了 6x3的，结果剩下 4x4和7x4都只能单溜
6x5套4x4，让7x4去套6x3，这样是最优解
因为是盒子，有两个维度，面积大小和能套与否没有线性关系，所以贪婪法不可以。
如果是一维的线条，或者都是正方形的盒子(等于是退化成一维的情况)，那就可以了
【在 r******j 的大作中提到】
: 9*9套3*6
: 2*8
: greedy可以啊 总是套下一个能套进去的面积最大的 为什么不可以？
|
d****n
发帖数: 233 | 16 抛个砖：
typedef struct {
int L;
int W;
} Dimension;
bool compareLW(const Dimension &l, const Dimension &r)
{
if (l.L == r.L) return l.W > r.W;
return l.L > r.L;
}
void normalize(Dimension &dimen)
{
if (dimen.L > dimen.W) {
int t = dimen.L;
dimen.L = dimen.W;
dimen.W = t;
}
}
int MinArea(vector dimens)
{
if (dimens.size() < 1) return 0;
for(int i = 0; i < dimens.size(); i++)
normalize(dimens[i]);
// Sort by Length, then Width
sort(dimens, compareByLW);
int sum1 = dimens[0].L * dimens[0].W;
int prev = 0;
for(int i = 1; i < dimens.size(); i++)
{
if(dimens[i].W > dimens[prev].W)
{
prev = i;
sum1 += dimens[i].L * dimens[i].W;
}
}
return sum
}
Complexity is O(NlogN)
【在 c*******e 的大作中提到】
: 6x5
: 7x4
: 6x3
: 4x4
: 这个例子，贪婪法会失败
: 因为 6x5的套了 6x3的，结果剩下 4x4和7x4都只能单溜
: 6x5套4x4，让7x4去套6x3，这样是最优解
: 因为是盒子，有两个维度，面积大小和能套与否没有线性关系，所以贪婪法不可以。
: 如果是一维的线条，或者都是正方形的盒子(等于是退化成一维的情况)，那就可以了
|
s***m
发帖数: 336 | 17 答案为什么是7*7+4*6？
而不是答案是7*7+4*6+3*3？4*6里面不是还能套一个吗？不太明白。求高人指点 。 |
s***m
发帖数: 336 | 18 还有，“最小面积放所有盒子”是什么意思？面积不是由最外面的大盒子决定的吗？ |
J******u
发帖数: 42 | |
