Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • World
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor

  • Default (No Skin)
  • No Skin
Collapse
Code Project
  1. Home
  2. General Programming
  3. C / C++ / MFC
  4. Dynamic programming fill 3D array

Dynamic programming fill 3D array

Scheduled Pinned Locked Moved C / C++ / MFC
helptutorialalgorithmsdata-structures
1 Posts 1 Posters 0 Views 1 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • P Offline
    P Offline
    pro grimi
    wrote on last edited by
    #1

    Hello, I'm trying to solve the 3 subset sum problem witch dynamic programming using a 3D array but I don't really now which rules to use to fill the array, can someone please help me to figure out the rules. Example (I need 3 subsets such that they have same sum) Input: {2,2,1,1} A = {2} B = {2} C = {1,1} Return: true How I understand it: With 3D array I'm searching if I can find 2 Subsets with sum = TotalSum/3 each. But how to fill the array, which rules should I use :confused:

    int subSetsFound(int n, int set[], int sum1, int sum2) {
    //n is n-1 (sum1 and sum2 are TotalSum/3)
    //cuboid[n][i][j] tells whether first set can have sum i and second - sum j in set = n
    int cuboid[sum1+1][sum2+1][n+1];

    // initialize top row/depth as true
    for (int i = 0; i <= n; i++) {
    	cuboid\[0\]\[0\]\[i\] = 1;
    }
    
    // initialize two leftmost columns (one in depth), except cuboid\[0\]\[0\]\[0\] and cuboid\[0\]\[1\]\[0\], as 0 (false)
    for (int i = 1; i <= sum1; i++) {
    	cuboid\[i\]\[0\]\[0\] = 0;
    	cuboid\[0\]\[i\]\[0\] = 0;
    }
    

    //not sure if I should do this
    for (int i = 0; i <= sum1; i++) {
    for (int j = 1; j <= sum2; j++) {
    cuboid[0][j][i] = 0;
    }
    }

    for (int i = 1; i <= sum1; i++) {
    	for (int j = 0; j <= sum2; j++) {
    		for (int k = 1; k <= n; k++) {
    			cuboid\[i\]\[j\]\[k\] = cuboid\[i\]\[j\]\[k-1\];
         		if (i - set\[k-1\] >= 0)
          			cuboid\[i\]\[j\]\[k\] = cuboid\[i\]\[j\]\[k\] || cuboid\[ j-set\[k-1\] \] \[j\] \[k-1\];
      
    			/\* This is for 2-sub-set problem
    			if (i-S\[j-1\]) >= 0
                P(i, j) ← P(i, j-1) или P(i-S\[j-1\], j-1)
                P(i, j) ← P(i, j-1)
    			\*/
    		}
    
    	}
    }
    
    return cuboid\[sum1\]\[sum2\]\[n\];//first set have sum = sum1 and second sum = sum2, so there are two subsets such that the sum is equal
    
    1 Reply Last reply
    0
    Reply
    • Reply as topic
    Log in to reply
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes


    • Login

    • Don't have an account? Register

    • Login or register to search.
    • First post
      Last post
    0
    • Categories
    • Recent
    • Tags
    • Popular
    • World
    • Users
    • Groups