Wednesday, June 20, 2012

动态规划之背包问题【3】

背包问题的下一个变体是二维背包问题!

二维背包问题的描述如下:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为w[i]。

他的解法很直接,因为状态多了一维,可以在状态上加一维!假设f[i][u][v]为前i个物品,且付出u和v费用时的最大价值!状态转移方程如下:

f[i][v][u]=max( f[i-1][v][u], f[i-1][v-a[i]][u-b[i]]+w[i] );

上面这个方程的空间复杂度是O(N^3),我们可以用01背包中那个逆向循环的办法,把三维的方程转化成二维的。
应对总个数的限制

“二维费用”的条件有时是以这样一种隐含的方式给出的:最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用,每个物品的件数费用均为1,可以付出的最大件数费用为M。换句话说,设f[v][m]表示付出费用v、最多选m件时可得到的最大价值,则根据物品的类型(01、完全、多重)用不同的方法循环更新,最后在f[0..V][0..M]范围内寻找答案。Source
所以,当发现由熟悉的动态规划题目变形得来的题目时,在原来的状态中加一纬以满足新的限制是一种比较通用的方法。

下面给出一个二维背包的题目:


Description

The NASA Space Center, Houston, is less than 200 miles from San Antonio, Texas (the site of the ACM Finals this year). This is the place where the astronauts are trained for Mission Seven Dwarfs, the next giant leap in space exploration. The Mars Odyssey program revealed that the surface of Mars is very rich in yeyenum and bloggium. These minerals are important ingredients for certain revolutionary new medicines, but they are extremely rare on Earth. The aim of Mission Seven Dwarfs is to mine these minerals on Mars and bring them back to Earth.
The Mars Odyssey orbiter identified a rectangular area on the surface of Mars that is rich in minerals. The area is divided into cells that form a matrix of n rows and m columns, where the rows go from east to west and the columns go from north to south. The orbiter determined the amount of yeyenum and bloggium in each cell. The astronauts will build a yeyenum refinement factory west of the rectangular area and a bloggium factory to the north. Your task is to design the conveyor belt system that will allow them to mine the largest amount of minerals.
There are two types of conveyor belts: the first moves minerals from east to west, the second moves minerals from south to north. In each cell you can build either type of conveyor belt, but you cannot build both of them in the same cell. If two conveyor belts of the same type are next to each other, then they can be connected. For example, the bloggium mined at a cell can be transported to the bloggium refinement factory via a series of south-north conveyor belts.
The minerals are very unstable, thus they have to be brought to the factories on a straight path without any turns. This means that if there is a south-north conveyor belt in a cell, but the cell north of it contains an east-west conveyor belt, then any mineral transported on the south-north conveyor beltwill be lost. The minerals mined in a particular cell have to be put on a conveyor belt immediately, in the same cell (thus they cannot start the transportation in an adjacent cell). Furthermore, any bloggium transported to the yeyenum refinement factory will be lost, and vice versa.
Image
Your program has to design a conveyor belt system that maximizes the total amount of minerals mined,i.e., the sum of the amount of yeyenum transported to the yeyenum refinery and the amount of bloggium transported to the bloggium refinery.

Input

The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 500 of rows, and the number 1 ≤ m ≤ 500 of columns. The next n lines describe the amount of yeyenum that can be found in the cells. Each of these n lines contains m integers. The first line corresponds to the northernmost row; the first integer of each line corresponds to the westernmost cell of the row. The integers are between 0 and 1000. The next n lines describe in a similar fashion theamount of bloggium found in the cells.
The input is terminated by a block with n = m = 0.

Output

For each test case, you have to output a single integer on a separate line: the maximum amount of mineralsthat can be mined.

Sample Input

4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
0 0

Sample Output

98

Hint

Huge input file, 'scanf' recommended to avoid TLE.

Source: Central Europe 2005

这个题目很经典,而且已经有了不少代码了解决这个问题!下面我给出我的思路,代码稍后会给出!


假设在某个状态i,整个系统的解可以由状态i-1得出,可以看下图:


image


As we could see from this figure. In state i-1, each block, marked by black, may have a N wealth, or W wealth, or both. In iteration i, we need to decide the transportation for the position marked by red and where the blue arrows placed. The red block can either be W or N. Because no matter what we place there, the new result will not bad than the previous one. If we place a W convey path in the red block, the blocks lower than it will be W for sure. Then, we only need to consider the W convey path, from the red block, ends at which block on the right. For example, if the red block points to N, all the path on right should be to N. The only variable here is the path to N, on i-th column, ends at which block. If it ends at K, all the wealth in i-1 to W of top K blocks is omitted. At the same time, K blocks of wealth to N is added to the total wealth. We need to find the value of K and the direction of the red block.


We could write a state transaction formula as follows:


wealth[i] = max( argmaxi<k<width( wealth[i-1] – sum( wealth to N, from i to K ) + sum( wealth to W on i row, from i to K ) ),  argmaxi<k<height( wealth[i-1] – sum( wealth to W, from i to K ) + sum( wealth to N on i column, from i to K ) ) );

No comments:

Post a Comment