EB3 2016年十二月第3绿 TSC PD 10/2012# EB23 - 劳工卡
l*6
1 楼
问一道题～
2D knapsack
class rect{
public:
int width;
int height;
int area;
};
input: vector source , int canvasWidth , int canvasHeight
no overlap allowed , no rotate allowed, each rect int source and be used as
many times as
possible (area = width * height , setting area as another val will be a
similar problem)
compute the max coverage of canvas using the rects int the source
a dp solution
maxCover[row][col] = max (maxCover[subRow][col] + maxCover[row - subRow - 1]
[col]) subRow in [0 , (row - 1)/2]
maxCover[row][col] = max (maxCover[row][subCol] + maxCover[row][col - subCol
- 1]) subCol in [0 , (col - 1)/2]
maxCover
int coverage(const vector &source , int canvasWidth , int canvasHeight)
{
vector> maxCover (canvasHeight , vector(canvasWidth , 0)
);
for(int row = 0 ; row < canvasHeight ; row ++)
{
for(int col = 0 ; col < canvasWidth ; col ++)
{
for(int idx = 0 ; idx < source.size() ; idx ++)
{
if(row + 1 >= source[idx].height && col + 1 >= source[idx].
width)
maxCover[row][col] = max(maxCover[row][col] , source[
idx].area);
}
}
}
for(int row = 0 ; row < canvasHeight ; row ++)
{
for(int col = 0 ; col < canvasWidth ; col ++)
{
for(int subRow = 0 ; subRow <=(row - 1)/ 2 ; subRow ++)
maxCover[row][col] = max(maxCover[row][col] , maxCover[
subRow][col] + maxCover[row - subRow - 1][col]);
for(int subCol = 0 ; subCol <= (col - 1)/2 ; subCol ++; )
maxCover[row][col] = max(maxCover[row][col] , maxCover[row]
[subCol] + maxCover[row][col - subCol - 1]);
}
}
return maxCover[canvasHeight - 1][canvasWidth - 1];
}
my problem : any optimal solution of a rectangle canvas is the sum of two
optimal solution of two sub rectangle canvas (either vertical of horizontal)
what if the optimal solution cannot be formed by sum of two optimal solution
of two sub rectangle canvas?
e.g rect1 . width 5 , height 8 , rect 2 width 8 , height 5 rect 3 width 3
, height 3
canvas: 13 by 13
optimal
______________
| 8 by 5 | 8 |
|________| by |
| | | 5 |
| |___ |_____|
| | |
|_____|________|
mid is a 3 by 3 square
2D knapsack
class rect{
public:
int width;
int height;
int area;
};
input: vector
no overlap allowed , no rotate allowed, each rect int source and be used as
many times as
possible (area = width * height , setting area as another val will be a
similar problem)
compute the max coverage of canvas using the rects int the source
a dp solution
maxCover[row][col] = max (maxCover[subRow][col] + maxCover[row - subRow - 1]
[col]) subRow in [0 , (row - 1)/2]
maxCover[row][col] = max (maxCover[row][subCol] + maxCover[row][col - subCol
- 1]) subCol in [0 , (col - 1)/2]
maxCover
int coverage(const vector
{
vector
);
for(int row = 0 ; row < canvasHeight ; row ++)
{
for(int col = 0 ; col < canvasWidth ; col ++)
{
for(int idx = 0 ; idx < source.size() ; idx ++)
{
if(row + 1 >= source[idx].height && col + 1 >= source[idx].
width)
maxCover[row][col] = max(maxCover[row][col] , source[
idx].area);
}
}
}
for(int row = 0 ; row < canvasHeight ; row ++)
{
for(int col = 0 ; col < canvasWidth ; col ++)
{
for(int subRow = 0 ; subRow <=(row - 1)/ 2 ; subRow ++)
maxCover[row][col] = max(maxCover[row][col] , maxCover[
subRow][col] + maxCover[row - subRow - 1][col]);
for(int subCol = 0 ; subCol <= (col - 1)/2 ; subCol ++; )
maxCover[row][col] = max(maxCover[row][col] , maxCover[row]
[subCol] + maxCover[row][col - subCol - 1]);
}
}
return maxCover[canvasHeight - 1][canvasWidth - 1];
}
my problem : any optimal solution of a rectangle canvas is the sum of two
optimal solution of two sub rectangle canvas (either vertical of horizontal)
what if the optimal solution cannot be formed by sum of two optimal solution
of two sub rectangle canvas?
e.g rect1 . width 5 , height 8 , rect 2 width 8 , height 5 rect 3 width 3
, height 3
canvas: 13 by 13
optimal
______________
| 8 by 5 | 8 |
|________| by |
| | | 5 |
| |___ |_____|
| | |
|_____|________|
mid is a 3 by 3 square
