c**********e
发帖数: 2007 | 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********m
发帖数: 15480 | |
p*****2
发帖数: 21240 | 3
虫子是DP大牛呀。这题我先想想再向你请教
【在 a********m 的大作中提到】
: 典型的背包。
|
a********m
发帖数: 15480 | 4 真不牛。
【在 p*****2 的大作中提到】
:
: 虫子是DP大牛呀。这题我先想想再向你请教
|
b******u
发帖数: 81 | 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**x
发帖数: 16 | 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**********e
发帖数: 2007 | 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********m
发帖数: 15480 | 8 上限k感觉没用。应该不需要保证非负。感觉这个dp本质是暴力法。 |
p*****2
发帖数: 21240 | 9 这题写起来还是很麻烦的。
准备一会儿练练。不知道面试考到的可能性大不大。 |
p*****2
发帖数: 21240 | 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******n
发帖数: 3946 | 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; i
for (int j=0; j
dp[i][j]=MAX_INT;
for (int i=0; i
int 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****9
发帖数: 164 | 12 can we sort it then do a linear parse to get partition? use bucket sort |
p*****2
发帖数: 21240 | 13
how to do linear parse?
【在 c****9 的大作中提到】
: can we sort it then do a linear parse to get partition? use bucket sort
|
a********m
发帖数: 15480 | 14 感觉排序以后从小到大扫一遍就可以了。
【在 c****9 的大作中提到】
: can we sort it then do a linear parse to get partition? use bucket sort
|
s*********5
发帖数: 514 | 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********r
发帖数: 277 | 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*****2
发帖数: 21240 | 17
backtrack我的solution里边有。
【在 s********r 的大作中提到】
: 怎么track具体的solution啊，就是哪个是你的集合。我一直觉得dp track solution
: 不怎么好写
|
