Last Updated on March 28, 2022 by Ria Pathak
CONCEPTS USED:
Dynamic programming.
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Arnab is now given N numbers, which are actually stacks of coins containing
a[i]amount of coins each. Now he is asked to choose any subset of the stacks of coins. But there is a problem Arnab has two brothers and he has to divide the coins equally into three divisions. Find the largest sum of coins which satisfies the above conditions.
For Example :
1
3
1 4 2
The set {2,4} is the only possible maximum set,
so there are 6 coins which can be divided into three equal groups.SOLVING APPROACH:
You are advised to do Maximum Subset Sum using Recursion (if you haven’t) first and then come to this problem .
- You have to find subsets for an array , whose sum is divisible by 3.
- As there can be many such subsets , print one with maximum sum.
You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.
See original problem statement here
BRUTE FORCE:
Let’s define a function
f(i,sum)where i is the current index and sum ranges from 0 to 2, which is the remainder obtained by dividing it with 3.For every index i ,
a[i]will either be included in the sum or not included.If it is not included,then
increase the index and recur further.If included, then
f(i,sum)will be the maximum ofa[i]not included anda[i]+solve(i+1,(sum+a[i])%3,v).Brute force approach will take exponential time to calculate the required sum.But if we use recursion with memoization ,we can optimize it.
Before proceeding to the solution we can see that the recursive solution will thake exponential time
(without memoization)so we will proceed to the dynamic programming approach.
Refer to the code for implementation.
#include <stdio.h>
int max(int x,int y)
{
if(x>y)return x;
return y;
}
int n;
int dp[40001][3];
int solve(int i,int sum,int v[]){
if(i==n)return 0;
if(dp[i][sum]!=-1)return dp[i][sum];
int ans=0;
if((sum+solve(i+1,sum,v))%3==0){
ans=solve(i+1,sum,v);
}
if((sum+v[i]+solve(i+1,(sum+v[i])%3,v))%3==0){
ans=max(ans,v[i]+solve(i+1,(sum+v[i])%3,v));
}
return dp[i][sum]=ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
memset(dp,-1,sizeof dp);
printf("%d\n",solve(0,0,arr));
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[40001][3];
int solve(int i,int sum,int v[]){
if(i==n)return 0;
if(dp[i][sum]!=-1)return dp[i][sum];
int ans=0;
if((sum+solve(i+1,sum,v))%3==0){
ans=solve(i+1,sum,v);
}
if((sum+v[i]+solve(i+1,(sum+v[i])%3,v))%3==0){
ans=max(ans,v[i]+solve(i+1,(sum+v[i])%3,v));
}
return dp[i][sum]=ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
memset(dp,-1,sizeof dp);
cout<<solve(0,0,arr)<<endl;
}
return 0;
}
import java.util.*;
class solution{
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int dp[][]=new int[40001][3];
int n;
int t=sc.nextInt();
while(t-->0)
{
n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
System.out.println(solve(0,0,arr,dp,n));
}
}
static int solve(int i,int sum,int v[],int dp[][],int n){
for(int k=0;k<dp.length;k++){
for(int j=0;j<dp[0].length;j++){
dp[k][j]=-1;
}
}
if(i==n)
return 0;
if(dp[i][sum]!=-1)
return dp[i][sum];
int ans=0;
if((sum+solve(i+1,sum,v,dp,n))%3==0){
ans=solve(i+1,sum,v,dp,n);
}
if((sum+v[i]+solve(i+1,(sum+v[i])%3,v,dp,n))%3==0){
ans=Math.max(ans,v[i]+solve(i+1,(sum+v[i])%3,v,dp,n));
}
return dp[i][sum]=ans;
}
}
dp = [[-1 for i in range(40001)] for j in range(3)] def solve(i, sum, v): if(i == n): return 0 if(dp[i][sum] != -1): return dp[i][sum] ans = 0 if((sum + solve(i + 1, sum, v)) % 3 == 0): ans = solve( i+1, sum, v) if((sum + v[i] + solve(i + 1, (sum + v[i]) % 3, v)) % 3 == 0): ans = max(ans, v[i] + solve(i + 1, (sum + v[i]) % 3, v)) dp[i][sum]=ans return dp[i][sum] for _ in range(int(input())): n = int(input()) arr = list(map(int, input().split())) print(solve(0, 0, arr))
Space complexity – O(N*N).
[forminator_quiz id="2165"]
This article tried to discuss the concept of Dynamic programming. Hope this blog helps you understand the concept of Dynamic programming. To practice more problems you can check out MYCODE|competitive programming