Need help in a simple DP question please!

help
, ,
1

I am really stucked at this problem as I just started solving Dp question. I would really be thankful if you can help me with the DP approach…

You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought.
Input Format. The first line contains an integer 𝑛. The second line contains integers 𝑣1, 𝑣2, . . . , 𝑣𝑛 separated by spaces.
Constraints. 1 ≤ 𝑛 ≤ 20, 1 ≤ 𝑣𝑖 ≤ 30 for all 𝑖.
Output Format. Output 1, if it possible to partition 𝑣1, 𝑣2, . . . , 𝑣𝑛 into three subsets with equal sums, and 0 otherwise.
Example:
Input:
4
3 3 3 3
Output:
0

2

This is only possible if n is a multiple of 3 and sum of array numbers is also a multiple of 3

3

Yes, but I want to know what to do next?

4

example:
3
9 3 3
@mri_999 here your explanation fails bro…

5

No it does not fail.
9 + 3 + 3 = 15
15/3 = 5
Output = 1 ( can be evenly split)

EVENLY SPLIT does not mean that you should get an even number after your split. It just means that you should be able to divide the number with 0 remainder.

I think I haven’t properly understood the problem. Can you please send the link to the problem?
Why does the following testcase fail?
4
3 3 3 3

6

we should be able to divide into three subsets with equal sum

1 Like
7

ok thanks i will look into this

8

@kabirpathak the objects in the array cannot be broken. I mean if an element is 9 you have to use it fully.
here in this example it was 9 3 3
so you have to give 9 to any three person fully.

9

Oh ok. Understood now. Sorry for the previous comment.

1 Like
10

This is a standard multi dimensional knapsack.
Let dp[i][j][k]=1 mean that we can distribute the first i objects, and give j value to person 1, and k value to person 2. We don’t need the amount needed by person 3, as it is equal to the sum of the first i objects, -j-k
dp[i][j][k] will be true if
dp[i-1][j][k] is true(Giving this object to person 3)
dp[i-1][j-value[i]][k](Giving this object to person 1)
dp[i-1][j][k-value[i]](Giving this object to person 2)
Base case is dp[0][0][0]=true

Code 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector<int> seq(n);
    int sum=0;
    for(auto &x : seq){
        cin>>x;
        sum+=x;
    }
    if(sum%3!=0){
        cout<<"0";
        return;
    }
    int m=sum/3;
    vector<vector<vector<bool>>> dp(n+1, vector<vector<bool>>(m+1, vector<bool>(m+1, 0)));
    //bool[n+1][m+1][m+1] with all values 0
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=m;k++){
                dp[i+1][j][k]=dp[i][j][k];
                if(j>=seq[i]){
                    dp[i+1][j][k]=dp[i+1][j][k]|dp[i][j-seq[i]][k];
                }
                if(k>=seq[i]){
                    dp[i+1][j][k]=dp[i+1][j][k]|dp[i][j][k-seq[i]];
                }
            }
        }
    }
    cout<<dp[n][m][m];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Time complexity O(n^xmax(V)^{x-1}/x^{x-1}) Where x is the number of people(3).

1 Like
11

Thank you so much! I was trying it for 2 days…