If I was given a array of positive integer, like [2,19,6,16,5,10,7,4,11,6], I wish to find the biggest subset sum attainable from the above array so that the sum is divisible by 3. I try to solve it using dynamic programming
let dp[i][j] to be the biggest sum attained up to index i in array with remainder of j, which is 0,1,2 since I am finding something divisible by 3.
And I have two implementation below:
int n = nums.length;
int[][] dp = new int[n+1][3];
dp[0][0] = 0;
dp[0][1] = Integer.MIN_VALUE;
dp[0][2] = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++) {
int remain = nums[i-1] % 3;
int remainder = (j + 3 - remain) % 3;
dp[i][j] = Math.max(dp[i-1][remainder] + nums[i-1], dp[i-1][j]);
}
}
return dp[n][0];
int n = nums.length;
int[][] dp = new int[n+1][3];
dp[0][0] = nums[0] % 3 == 0 ? nums[0] : Integer.MIN_VALUE;
dp[0][1] = nums[0] % 3 == 1 ? nums[0] : Integer.MIN_VALUE;
dp[0][2] = nums[0] % 3 == 2 ? nums[0] : Integer.MIN_VALUE;
for(int i = 1; i < n; i++) {
for(int j = 0; j < 3; j++) {
int remain = nums[i] % 3;
int remainder = (j + 3 - remain) % 3;
dp[i][j] = Math.max(dp[i-1][remainder] + nums[i], dp[i-1][j]);
}
}
return dp[n-1][0] == Integer.MIN_VALUE ? 0 : dp[n-1][0];
Both implementation above was base on the fact that I either add nums[i] or not, and I add the nums[i] to the table with the corresponding remainder before/after I added nums[i], which is like knapsack DP, but the first version pass all test cases and the one below failed for some of them. Like [2,19,6,16,5,10,7,4,11,6], it gives 81 instead of the correct answer 84, can anyone explain why the second version is wrong?
The first version is calculating the largest subset sum divisible by 3; the second version calculates the largest sum divisible by 3 of a subset that includes nums[0], the first element.
The sole difference in the two versions is the base case for dynamic programming. The first version has the correct base cases: after processing zero elements, the only subset sum possible is zero. In the second version, the base case starts at 1, and implies that after processing one element, the only subset sum possible is the one containing that first element. All future subset sums are forced to use that element.
Try running the code on the array [1, 3]. The second version will return zero, because it does not consider subsets without 1.