USACO的一个动态规划问题

In section2.2,a problem called"subset sum"require you to calculate in how many ways can a integer set from 1 to n be partitioned into two sets whose sums are identical.

在section2.2中，一个名为“子集和”的问题要求您计算一个从1到n的整数集可以以多少种方式被划分为两个集合，它们的和是相同的。

I know the recurrence is:

我知道递归式是:

f[i][j] : numbers of ways that sum up to j with 1...i

f[i][j]: j和1…i的个数

f[i][j]=f[i-1][j]+f[i-1][j-i]

[我][j]= f(张)[j]+ f(张)[j-i]

if the initial condition is:

如果初始条件是:

f[1][1]=1;//others are all zero,main loop start from 2

f[1][1]=1;//其他都是0，主循环从2开始

OR:

或者:

f[0][0]=1;//others are all zero,main loop start from 1

f[0][0]=1;//其他都是0，主循环从1开始

the answers are all f[n][n*(n+1)/4].Does this means the initial condition doesn't affect the answer?

答案都是f[n][n*(n+1)/4]。这是否意味着初始条件不影响答案?

but if I use a one dimension array,say f[N]:

但如果我使用一维数组，比如f[N]:

let f[0]=1,loop from 1(so f[0] is f[0][0] in fact),the answer is f[n]/2

假设f[0]=1，从1开始循环(f[0]实际上是f[0][0])，答案是f[n]/2

or f[1]=1,loop from 2(f[1] is f[1][1]),the answer is f[n]

或者f[1]=1，循环2(f[1] = f[1][1])，答案是f[n]

I am so confused...

我很困惑…

1 个解决方案

#1

I don't know if you are still stuck on this problem, but here's a solution for anyone else who stumbles onto this problem.

我不知道你是否还困在这个问题上，但这里有一个解决方法，任何人都可以在这个问题上跌倒。

Let ways[i] be the number of ways you can get a sum of i using a subset of the numbers 1...N.

让方法[i]是你用1…N这个数字的子集得到i的和的个数。

Then it becomes a variant of the 0-1 knapsack algorithm:

然后它变成了0-1背包算法的一个变体:

base case: ways[0] = 1

基本情况:方法[0]= 1

for (int i = 1; i <= N; i++) {
    for (int j = sum - i; j >= 0; --j) { //sum is n*(n+1)/2
        ways[j + i] += ways[j];
    }
}

Your answer is located at ways[sum/2]/2.

你的答案位于[sum/2]/2处。

#1