动态规划背包思想求解

这道题可以利用背包思想。

首先x1,x2,x3,...,xn可以分为2个数组。

a1,a2,... 和b1,b2,... sum{a}+sum{b} = sum{x}而且 sum{a}-sum{b}=e，将两式相加得到sum{a} = (sum{x} + e ) / 2;

故先判断e是否大于sum，如果大于，则肯定无解，在判断sum{x}+e能否被2整除，不能则无解。

然后再使用背包的改良版本。

for(i = 1; i <= n; i++){

   for(j = target; j >= num[i]; j--){

          dp[j] = dp[j] + dp[j - num[i]];

   }

}

注意，以往这个公式式dp[j] = max(dp[j], dp[j-num[i]] + num[i])，但是求的是能够带来的最大价值。

而这次我们求的是解答的数量，公式发生了相应的变化。

而最麻烦的是，如何初始化这个dp数组。因为现在的公式是相加，而不是在公式里就加上了+num[i]；

我一开始认为初始化dp[num[1]]=1，但是感觉很奇怪，随后看了代码随想录发现，应该是dp[0]=1，这样在每一层循环的时候会自动给dp[num[i]]赋值，因为j=num[i]时，dp[j]至少会为1（dp[j-num[i]]是其中的加项之一）。

完整代码如下。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int mode = 1e9 + 7;

int n, e, ans;
int sum;
int cnt;
int dp[100005];
int num[100005];

int main() {
    int i, j;
    while (cin>>n){
        memset(dp, 0, sizeof (dp));
...