求艺龙编程题【数字分组】解法

    public static int getNum(int[] nums) {         if (nums == null || nums.length == 0) return 0;         int target = 0;         int n = nums.length;         for (int i = 0; i < nums.length; ++i) target += nums[i];         boolean[][] dp = new boolean[n + 1][target + 1];         dp[0][0] = true;         int i, j;         for (j = 1; j <= target; ++j) dp[0][j] = false;         for (i = 1; i <= n; ++i) {             for (j = 1; j <= target; ++j) {                 dp[i][j] = dp[i - 1][j];                 if (j >= nums[i - 1])                     dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i][j];             }         }         for (j = target; j >= 0; --j) {             if (dp[n][j] && dp[n][j / 2]) return j / 2;         }         return -1;     }

#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int dp[20000]; int a[200]; int main(){ int n; scanf("%d", &n); for(int i = 0; i < n; i++)scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); dp[0] = 1; for(int i = 0; i < n; i++){ for(int j = 2000; j >= a[i]; j--){ if(dp[j - a[i]])dp[j] = 1; } } int ans = 0; for(int i = 1; i <= 1000; i++){ if(dp[i] && dp[i * 2])ans = i; } if(ans > 0)printf("%d\n", ans); else printf("Impossible"); } dp[i]表示组得成和为i

？

40％ 想不通

样例 为什么不能是 1，3一组， 4一组，其余不用，这样不是输出4吗

动态规划，dp (i,j)表示前i个物品中两组相差为j是否成立，求出的dp(n，0)即为结果

1 1 2 3应该返回的是多少呢

bd，求个思路

跑容量是所有数的和的01背包，然后枚举分割后的数组中数的和

感觉不难，为啥写不出来呢

通过了30%😖😖😖

貌似动态规划，，

我咋调都是10%。。而且想不到除了暴力以外的做法。。