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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先按长的边sort,然后用求longest increasing subsequence
|
z***m 发帖数: 1602 | 5 我也只能想到这儿了
【在 G*****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 貌似不保证optimal吧
|
e***i 发帖数: 231 | 6 先按面积/length/width sort,然后dp?另外,相等的情况算可以套还是不可以?
似乎greedy不能保证length/width sort最优
9*9
2*8
3*6
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有若干个盒子,每个盒子有length和width,不考虑高度。只要尺寸fit,大盒子就可以 : 放小盒子,但是一层只能套一个,即便还有空余;但可以多层嵌套。求最小的面积放所 : 有的盒子 : 比如 7*7 5*5, 4*6, 3*3 : 答案是7*7+4*6 : 这个题目大家有没有什么好的解法,贪婪算法该怎么做呢? 多谢啦!
|
g*****y 发帖数: 1120 | 7 Dp貌似可以。recursive 最简单
【在 e***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先按面积/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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有若干个盒子,每个盒子有length和width,不考虑高度。只要尺寸fit,大盒子就可以 : 放小盒子,但是一层只能套一个,即便还有空余;但可以多层嵌套。求最小的面积放所 : 有的盒子 : 比如 7*7 5*5, 4*6, 3*3 : 答案是7*7+4*6 : 这个题目大家有没有什么好的解法,贪婪算法该怎么做呢? 多谢啦!
|
|
|
T*****u 发帖数: 7103 | 11 牛!
【在 j********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先按面积/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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | |