每日一题(19)――数组分割(动态规划) - 小熊不去实验室 - 博客频道 - CSDN.NET


一、问题:

      1. 有一个无序、元素个数为2n的正整数数组,要求:如何能把这个数组分割为两个子数组,子数组的元素个数不限,并使两个子数组之和最接近。
      2. 有一个无序、元素个数为2n的正整数数组,要求:如何能把这个数组分割为元素个数为n的两个数组,并使两个子数组之和最接近。
解法1:(小田)
分为几个阶段:
       外阶段:在前k1个数中进行选择,k1=1,2...2*n。
       内阶段:从这k1个数中任意选出k2个数,k2=1,2...k1。
       状态:这k2个数的和为s,s=1,2...sum/2。
       决策:决定这k2个数的和有两种决策,一个是这k2个数中包含第k1个数,另一个是不包含第k1个数。
这种做法与0-1背包的方法2相似。很厉害的方法,不需要判断一个节点是否已经使用过
dp[k][s]表示从前k个数中取任意个数,且这些数之和为s的取法是否存在。
  1. int main()  
  2. {  
  3.     int n, i, k1, k2, s, u;  
  4.     cin >> n;  
  5.     for (i=1; i<=2*n; i++)  
  6.         cin >> A[i];  
  7.     int sum = 0;  
  8.     for (i=1; i<=2*n; i++)  
  9.         sum += A[i];  
  10.     memset(dp,0,sizeof(dp));  
  11.     dp[0][0]=true;  
  12.         // 外阶段k1表示第k1个数,内阶段k2表示选取数的个数  
  13.          // 这跟前面陪审团和0-1背包的方法不太一样,他们是在外阶段(外循环)迭代选取个数,内阶段迭代具体选取那个数  
  14.          // 这样做需验证选取的数是否出现过,但是可以通过保存Path[个数][状态和]来存储各个状态;  
  15.     for (k1=1; k1<=2*n; k1++)            // 外阶段k1  
  16.     {  
  17.         for (k2=k1; k2>=1; k2--)     // 内阶段k2  
  18.             for (s=1; s<=sum/2; s++) // 状态s  
  19.             {  
  20.                 //dp[k1][s] = dp[k1-1][s];  
  21.                 // 有两个决策包含或不包含元素k1  
  22.                 if (s>=A[k1] && dp[k2-1][s-A[k1]])  
  23.                     dp[k2][s] = true;  
  24.             }  
  25.     }  
  26.     /*根据0-1背包问题改写的方法:事实证明这种方法在不判断选用节点k2是否使用过的情况下,不可取,因为可能会重复调用某一个节点,除非再利用Path[k1][s]保存相应状态的节点。再判断它是否出过。那样的话,就需要用dp[k1][s]保存状态和s,也就是说跟第二个坐标一样。 
  27.     for (k1=0; k1<2*n; k1++)         // 迭代选取数量 
  28.     { 
  29.         for (s=0; s<=sum/2; s++)         // 状态和sum:s 
  30.             if(dp[k1][s]==true) 
  31.             for (k2=1; k2<=2*n; k2++)        // 选取第k2个    
  32.             { 
  33.                 if (s>=A[k1] )   // if(s>=A[k1] && dp[k2-1][s-A[k1]]) 
  34.                     dp[k1+1][s+A[k2]] = true; 
  35.             } 
  36.     } 
  37.     */  
  38.     // 之前的dp[k][s]表示从前k个数中取任意k个数,经过下面的步骤后  
  39.     // 即表示从前k个数中取任意个数  
  40.     for (k1=2; k1<=2*n; k1++)  
  41.         for (s=1; s<=sum/2; s++)  
  42.             if (dp[k1-1][s])  
  43.                 dp[k1][s]=true;  
  44.     // 确定最接近的给定值sum/2的和  
  45.     for (s=sum/2; s>=1 && !dp[2*n][s]; s--)  
  46.                ;  
  47.                  
  48.     printf("the differece between two sub array is %d\n", sum-2*s);  
  49. }  
解法2.
根据0-1背包问题方法2改写的算法:也好使~这种方式更简便!
只需要改动一点:利用dp[i][m]保存状态和,跟m的值一样。
依然无需测试一个节点是否已经存在,但依然无法保存路径,即无法输出最优解的过程
  1. struct{  
  2.     int wei;  
  3. }node[nMax];  
  4.   
  5. int main()  
  6. {  
  7.     int m, n, i ,w ,dp[mMax],sumN=0;  
  8.     while(cin>>n)  
  9.     {  
  10.         if(n==0) break;  
  11.         for (i=1; i<=2*n;i++)  
  12.         {  
  13.             cin>>node[i].wei;  
  14.             sumN += node[i].wei;  
  15.         }  
  16.         m=sumN/2;  
  17.   
  18.         memset(dp, 0, (m+1)*sizeof(int));  
  19.   
  20.         for (i=1; i<=2*n; i++)  
  21.             for ( w=m; w>=node[i].wei; w-- )//根据解法1的分析,必须将权重保存成下标才能满足最优化问题。  
  22.                 if ( dp[w] < dp[w - node[i].wei] + node[i].wei )  
  23.                     dp[w] = dp[w - node[i].wei] + node[i].wei;  
  24.   
  25.         cout<<dp[m]<<endl;  
  26.         cout<<"the differece between two sub array is: "<<sumN - 2*dp[m]<<endl;  
  27.     }  
  28. }
解法3,
根据公正陪审团问题改写的算法dp[k][s]:外循环是选取个数k,中间是状态和s,内循环是选取具体哪一个index;同时可以保存路径,输出具体选取哪些数字
  1. int A[MAXN];  
  2. int dp[MAXN][MAXSUM];  
  3. int Path[MAXN][MAXSUM];  
  4. // dp[k][s]表示取k个数,且和为s的情况下,保存的依然是和s;因为要优化判断  
  5. int main()  
  6. {  
  7.     int n, i, k1, k2, s, u,t1,t2;  
  8.     cin >> n;  
  9.     for (i=1; i<=2*n; i++)  
  10.         cin >> A[i];  
  11.     int sum = 0;  
  12.     for (i=1; i<=2*n; i++)  
  13.         sum += A[i];  
  14.     memset(dp,-1,sizeof(dp));  
  15.       
  16.     dp[0][0]=0;//初始状态  
  17.   
  18.     for (k1=0; k1<2*n; k1++)         // 选取的数量k1  
  19.     {  
  20.         for (s=0; s<=sum/2; s++)     // 状态和s  
  21.         if(dp[k1][s]>=0)  
  22.         {  
  23.             for (k2=1; k2<=2*n; k2++)        // 具体选取哪一个k2  
  24.                 if(dp[k1][s]+A[k2]>dp[k1+1][s+A[k2]] && s+A[k2]<=sum/2)  
  25.                 {  
  26.                     t1=k1;t2=s;  
  27.                     while(t1>0&&Path[t1][t2]!=k2)//验证k2是否在前面出现过  
  28.                     {  
  29.                         t2-=A[Path[t1][t2]] ;//减前一个元素的值  
  30.                         t1--;  
  31.                     }  
  32.                     if (t1==0)  
  33.                     {  
  34.                         dp[k1+1][s+A[k2]] = dp[k1][s]+A[k2];  
  35.                         Path[k1+1][s+A[k2]] = k2;       //k2保存在Path中  
  36.                     }  
  37.                 }  
  38.         }  
  39.     }  
  40.   
  41.     int maxS=0,maxN=0;  
  42.     for (k1=1; k1<=2*n; k1++)  
  43.         for (s=1; s<=sum/2; s++)  
  44.             if (dp[k1][s]>maxS)  
  45.             {  
  46.                 maxS=dp[k1][s];  
  47.                 maxN=k1;  
  48.             }  
  49.     cout<<"the count of num: "<<maxN<<"  the max sum of the num: "<<maxS<<endl;         
  50.     cout<<"the differece between two sub array is: "<< sum-2*maxS<<endl;  
  51.   
  52.     set<int> index;  
  53.     index.clear();  
  54.     for (int i=0; i<maxN; i++)  
  55.     {  
  56.         int id = Path[maxN-i][maxS];  
  57.         index.insert(id);  
  58.         maxS -= A[id];  
  59.     }  
  60.     cout<<endl;  
  61.     cout<<"the index of selected num: ";  
  62.     for(set<int>::iterator iter=index.begin(); iter!=index.end(); iter++) cout<<*iter<<" ";   
问题2.
解法1:
     但本题还增加了一个限制条件,即选出的物体数必须为n,这个条件限制了内阶段k2的取值范围,(同:公正陪审团问题)并且dp[k][s]的含义也发生变化。这里的dp[k][s]表示从前k个数中取任意不超过n的k个数,且这些数之和为s的取法是否存在
  1. #define MAXN 101  
  2. #define MAXSUM 100000  
  3. int A[MAXN];  
  4. bool dp[MAXN][MAXSUM];  
  5. // 题目可转换为从2n个数中选出n个数,其和尽量接近于给定值sum/2  
  6. int main()  
  7. {  
  8.     int n, i, k1, k2, s, u;  
  9.     cin >> n;  
  10.     for (i=1; i<=2*n; i++)  
  11.         cin >> A[i];  
  12.     int sum = 0;  
  13.     for (i=1; i<=2*n; i++)  
  14.         sum += A[i];  
  15.     memset(dp,0,sizeof(dp));  
  16.     dp[0][0]=true;  
  17.     // 对于dp[k][s]要进行u次决策,由于阶段k的选择受到决策的限制,  
  18.     // 这里决策选择不允许重复,但阶段可以重复,比较特别  
  19.     for (k1=1; k1<=2*n; k1++)                // 外阶段k1  
  20.         for (k2=min(k1,n); k2>=1; k2--)      // 内阶段k2  
  21.             for (s=1; s<=sum/2; s++) // 状态s  
  22.                 // 有两个决策包含或不包含元素k1  
  23.                 if (s>=A[k1] && dp[k2-1][s-A[k1]])  
  24.                     dp[k2][s] = true;  
  25.     // 确定最接近的给定值sum/2的和  
  26.     for (s=sum/2; s>=1 && !dp[n][s]; s--);  
  27.     printf("the differece between two sub array is %d\n", sum-2*s);  
问题1的解法3肯定适用,只要最后选择最大值时确定dp[k][s]的k即可;
问题公正陪审团问题1的解法2是否使用,还有待验证。

注意:如果数组中有负数的话,上面的背包策略就不能使用了(因为第三重循环中的s是作为数组的下标的,不能出现负数的),需要将数组中的所有数组都加上最小的那个负数的绝对值,将数组中的元素全部都增加一定的范围,全部转化为正数,然后再使用上面的背包策略就可以解决了。
这种带权重的求和的最优化问题,都可以转换为数组求和最优问题,(转化为判别划分问题)。
从具体的解法上来说,解法3,即公正陪审团问题的解法比较完善,可以保存路径,但是需要额外判断选取的某个数是否已经存在。且这种解法比较容易理解:
dp[k][s]:
外循环迭代k,表示取元素的个数;
中间循环迭代s:表示状态和s(限制条件,不能超过多少……)
内循环迭代index:表示具体是否选取A[index];
判别:+A[index]满足最优条件 &A[index]没有出现过(通过Path判别,保存)
最终:输出时若有个数限制K,则在dp[K][]中查找,若没有个数限制,则在dp[][]全部中查找
PS:利用Path输出路径时,可以先保存在set中,这样输出有序。
Read full article from 每日一题(19)——数组分割(动态规划) - 小熊不去实验室 - 博客频道 - CSDN.NET

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts