Another DP Problem: Balanced Partition - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Another DP Problem: Balanced Partition

Another DP Problem: Balanced Partition# JobHunting - 待字闺中

c*e2012-04-07 07:04

1 楼

•Balanced Partition:
Given a set of n integers, each in the range 0 ... K, partition the integers
into two subsets to minimize |S1 - S2|, where S1 and S2 denote the sums of
the elements in each of the two subsets.

a*m2012-04-07 07:04

2 楼

典型的背包。

p*22012-04-07 07:04

3 楼

虫子是DP大牛呀。这题我先想想再向你请教

【在 a********m 的大作中提到】

: 典型的背包。

a*m2012-04-07 07:04

4 楼

真不牛。

【在 p*****2 的大作中提到】

:
: 虫子是DP大牛呀。这题我先想想再向你请教

b*u2012-04-07 07:04

5 楼

public static List GetBag(List set)
{
List result = null;
int sum = set.Sum();
while (true)
{
int target = sum / 2;
result = GetSet(set, target);
if (result != null)
{
break;
}
else
{
target--;
}
}
return result;
}

z*x2012-04-07 07:04

6 楼

我的想法是：
1.设上限为 sum（1，n）/2
2.背包DP,求出子集A，such that for all possible subset A, ( sum(1,n)/2- A.sum
) is minimized
3.所以有A的补集B，（ B.sum-sum(1,n)/2）is minimized
4.所以对于这个partition， |A.sum - B.sum| is minimized
另外想请问背包问题的DP解法的前提是要保证物品的weight要不小于零吗（如本题的O
到K），另外这个上限K有没有实际的作用呢

c*e2012-04-07 07:04

7 楼

This is great. So the problem becomes to select a subset to minimize n*(n+1)
/2-A.sum.

sum
O

【在 z**x 的大作中提到】

: 我的想法是：
: 1.设上限为 sum（1，n）/2
: 2.背包DP,求出子集A，such that for all possible subset A, ( sum(1,n)/2- A.sum
: ) is minimized
: 3.所以有A的补集B，（ B.sum-sum(1,n)/2）is minimized
: 4.所以对于这个partition， |A.sum - B.sum| is minimized
: 另外想请问背包问题的DP解法的前提是要保证物品的weight要不小于零吗（如本题的O
: 到K），另外这个上限K有没有实际的作用呢

a*m2012-04-07 07:04

8 楼

上限k感觉没用。应该不需要保证非负。感觉这个dp本质是暴力法。

p*22012-04-07 07:04

9 楼

这题写起来还是很麻烦的。
准备一会儿练练。不知道面试考到的可能性大不大。

p*22012-04-07 07:04

10 楼

写了一下。很麻烦。面试碰到肯定死了。
import java.io.*;
import java.util.*;
public class BalancedPartition
{
public static void main(String[] args)
{
new BalancedPartition().run();
}
PrintWriter out = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
int[] A = new int[]
{ 1, 2, 3, 4, 5, 6 };
balancedPar(A, 7);
out.close();
}
void balancedPar(int[] A, int k)
{
int n = A.length;
Ele[][] dp = new Ele[n][n * k + 1];
for (int i = 0; i < n; i++)
for (int j = 0; j < n * k + 1; j++)
dp[i][j] = new Ele();
dp[0][A[0]].exist = true;
dp[0][A[0]].self = true;
for (int i = 0; i < n; i++)
if (A[i] == 0)
{
dp[i][0].exist = true;
dp[i][0].self = true;
}
for (int i = 1; i < n; i++)
for (int j = 1; j < n * k + 1; j++)
{
if (dp[i - 1][j].exist)
{
dp[i][j].exist = true;
dp[i][j].prev = i - 1;
}
else if (A[i] <= j && dp[i - 1][j - A[i]].exist)
{
dp[i][j].exist = true;
dp[i][j].prev = i - 1;
dp[i][j].self = true;
}
}
int sum = 0;
for (int i = 0; i < n; i++)
sum += A[i];
int half = sum / 2;
int max = 0;
int x = -1;
for (int j = 1; j <= half; j++)
{
for (int i = 0; i < n; i++)
{
if (dp[i][j].exist)
{
max = j;
x = i;
break;
}
}
}
out.println(max);
while (max > 0)
{
if (dp[x][max].self)
{
out.println(A[x] + " ");
max -= A[x];
}
x--;
}
}
}
class Ele
{
boolean exist;
int prev = -1;
boolean self;
}

s*n2012-04-07 07:04

11 楼

这个题目能用DP的关键是每个数都大于等于0：
总和为sum
A(i,Y) 表示前i项选任意个之和小于Y且与Y最接近的差。
所以我们要求：A(N, sum/2)
递推:
A(i, Y) = min(A(i-1, Y), A(i-1, Y-a[i]))
代码
============================================
dp[N][SUM/2];
for (int i=1; ifor (int j=0; jdp[i][j]=MAX_INT;
for (int i=0; iint calculate(int i, int sum)
{
if (dp[i,sum]!=MAX_INT) return dp[i,sum];
assert(i>0);
int solution1 = calculate(i-1, sum);
int solution2 = MAX_INT;
if (Y>a[i]) solution2 = calculate(i-1, Y-a[i]);
if (solution1 < solution2) return dp[i,sum]=solution1;
else return dp[i,sum]=solution2;
}

c*92012-04-07 07:04

12 楼

can we sort it then do a linear parse to get partition? use bucket sort

p*22012-04-07 07:04

13 楼

how to do linear parse?

【在 c****9 的大作中提到】

: can we sort it then do a linear parse to get partition? use bucket sort

a*m2012-04-07 07:04

14 楼

感觉排序以后从小到大扫一遍就可以了。

【在 c****9 的大作中提到】

: can we sort it then do a linear parse to get partition? use bucket sort

s*52012-04-07 07:04

15 楼

Suppose you have two group divided, to reduce the current distance between
the group, S1, S2, you need be able to swap two elements in the two group.
Therefore, we should reserve the pair of numbers with the smallest distance.
So an algorithm should be to sort the numbers first, then divide them into
pairs, starting from the smallest distance available. Then divide each pair
into the two groups.
nlog + n

s*r2012-04-07 07:04

16 楼

怎么track具体的solution啊，就是哪个是你的集合。我一直觉得dp track solution
不怎么好写

【在 s******n 的大作中提到】

: 这个题目能用DP的关键是每个数都大于等于0：
: 总和为sum
: A(i,Y) 表示前i项选任意个之和小于Y且与Y最接近的差。
: 所以我们要求：A(N, sum/2)
: 递推:
: A(i, Y) = min(A(i-1, Y), A(i-1, Y-a[i]))
: 代码
: ============================================
: dp[N][SUM/2];
: for (int i=1; i

p*22012-04-07 07:04

17 楼

backtrack我的solution里边有。

【在 s********r 的大作中提到】

: 怎么track具体的solution啊，就是哪个是你的集合。我一直觉得dp track solution
: 不怎么好写