Massive Algorithms: DP-Include vs Exclude

Showing posts with label DP-Include vs Exclude. Show all posts

Algorithms Forever ...: Largest sum of elements with no three consecutive

Given a sequence of positive numbers, find the maximum sum that can be formed which has no 3 consecutive elements present.

For example: consider the sequence 3000 2000 1000 3 10 Here, the answer would be 5013, by taking 3000, 2000, 3 & 10. Note that we can't form a sequence that takes 3000, 2000 & 1000 together because they are the consecutive elements of the array.

Sample cases 1 2 3 ans=5

100 1000 100 1000 1 ans=2101

1 1 1 1 1 ans=4

1 2 3 4 5 6 7 8 ans=27

Try to find an O(N) solution. N is the number of elements in the array.

int max_three(int[] input, int N){

int sum[] = new int[N+2];

sum[0] = 0;

sum[1] = input[0];

sum[2] = input[0] + input[1];

for (int i=2; i<N ;++i){

sum[i+1] = max(input[i] + sum[i-1], input[i] + input[i-1] + sum[i-2]);

sum[i+1] = max(sum[i+1], sum[i]);

}

return sum[N];

}
Read full article from Algorithms Forever ...: Largest sum of elements with no three consecutive

Maximum sum such that no two elements are adjacent - GeeksforGeeks

Maximum sum such that no two elements are adjacent - GeeksforGeeks
Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

includeSum[k] = excludeSum[k-1] + data[i]
excludeSum[k] = Max(includeSum[k-1], excludeSum[k-1])

That said, we don't need to keep an array of previous maximum sums. All we need are just previous includeSum and excludeSum.

http://www.fgdsb.com/2015/01/03/find-max-values/

跟栅栏上色问题是一样的，只关心上一个和上上一个记录，所以不需要O(n)的space，O(1)足矣。
这题还有这样一种表达：
有一溜n个房子，每个房子里面的东西的value是给定的一个正整数，小偷准备去偷东西来maximize gain，但是有一个条件是不能偷连续两幢房子的东西，因为房主挨偷以后会告诉左右邻居。要求给出能偷到的最大value的值。

int FindMaxSum(int arr[], int n)

{

  int incl = arr[0];

  int excl = 0;

  int excl_new;

  int i;

  for (i = 1; i < n; i++)

{

     /* current max excluding i */

     excl_new = (incl > excl)? incl: excl;

     /* current max including i */

     incl = excl + arr[i];

     excl = excl_new;

}

   /* return max of incl and excl */

   return ((incl > excl)? incl : excl);

}

http://tech-queries.blogspot.com/2009/05/max-possible-sum-of-non-consecutive.html

If we denote the ith element as T(i) and max sum till ith element of the array as S(i), then

S(i) = MAX {S(i-1), S(i-2) + T(i) }
S(-1) = 0;
if i=0, S(i) = T(0);


int max_value(const vector<int>& nums) {

if(nums.empty()) return 0;

int prev_prev = 0, prev = nums[0];   

for(int i = 1; i < nums.size(); ++i) {

int old_prev = prev;

prev = max(prev, max(nums[i] + prev_prev, prev));

prev_prev = old_prev;

}   

return prev;

}

O(n^2) time and O(n) spaces:
http://n00tc0d3r.blogspot.com/2013/07/maximum-sum-of-non-contiguous.html
One way to improve is to use backtracking: Store the known maxSum for subarrays we have visited, [0 .. k]. More specifically,

maxSum[k] = maximum sum of subsequences of array [0 .. k] that include array[k].

Now the algorithm becomes:

For each element in the array, find the maximum sum of array[k]+maxSum[j] where 0 <= j < k-1.
Notice that maxSum[k-1] includes array[k-1] and thus it cannot include array[k].

 public int maxSumInSubsequence(int[] data) {  
   if (data == null) return 0;  
   int n = data.length;  
   
   // maxSum[i] == the maximum sum of subsequences of data[0 .. i] that include data[i]  
   int[] maxSum = new int[n];  
   for (int i=0; i<n; ++i) {  
     maxSum[i] = data[i];  
     // maxSum[i-1] includes data[i-1] and thus cannot include data[i]  
     for (int j=0; j<i-1; ++j) {  
       maxSum[i] = Math.max(data[i] + maxSum[j], maxSum[i]);  
     }  
   }  
   
   // find the max of all subsequences  
   int max = 0;  
   for (int i=0; i<n; ++i) {  
     max = Math.max(max, maxSum[i]);  
   }  
   
   return max;  
 }

Extension:
Max non-contiguous sum with loop
TopCoder Dynamic Programming Bad Neighbours Donation Collection Problem
http://justprogrammng.blogspot.com/2015/02/topcoder-dynamic-programming-bad.html
http://www.krishnabharadwaj.info/dynamic-programming/
Same as Leetcode House Rubber II: http://massivealgorithms.blogspot.com/2015/05/leetcode-213-house-robber-ii-csdnnet.html
Read full article from Maximum sum such that no two elements are adjacent - GeeksforGeeks

Lintcode: Backpack I,II,III,IV,V

https://zhengyang2015.gitbooks.io/lintcode/backpack_i_92.html

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Notice

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

https://www.cnblogs.com/lz87/p/6928227.html

State: T[i][j]: the max size we can get out of the first i items when the backpack size is j.

Function: T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - A[i - 1]] + A[i - 1]), if j >= A[i - 1];

T[i][j] = T[i - 1][j], if j < A[i - 1].

Initialization: T[i][0] = T[0][j] = 0

Answer: T[A.length][m]

public int backPack(int m, int[] A) {

if (A == null || A.length == 0) {

return 0;

}

int[][] T = new int[A.length + 1][m + 1];

for (int i = 0; i <= A.length; i++) {

T[i][0] = 0;

}

for (int j = 0; j <= m; j++) {

T[0][j] = 0;

}

for (int i = 1; i <= A.length; i++) {

for (int j = 1; j <= m; j++) {

if (j >= A[i - 1]) {

T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - A[i - 1]] + A[i - 1]);

} else {

T[i][j] = T[i - 1][j];

}

return T[A.length][m];

}

for j, we can also from m to 1

public int backPack(int m, int[] A) {

if (A == null || A.length == 0) {

return 0;

}

int[][] T = new int[A.length + 1][m + 1];

for (int i = 0; i <= A.length; i++) {

T[i][0] = 0;

}

for (int j = 0; j <= m; j++) {

T[0][j] = 0;

}

for (int i = 1; i <= A.length; i++) {

for (int j = m; j >= m; j--) {

if (j >= A[i - 1]) {

T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - A[i - 1]] + A[i - 1]);

} else {

T[i][j] = T[i - 1][j];

}

return T[A.length][m];

}

-- should change the order m, n
基础背包类问题，用DP解。两种方法本质都一样，只是表述不同。

第一种方法为dp[i][j]表示i容量的背包在j件物品中能取的最大值。分两种情况：一种情况为不要第j件物品，则最优情况为背包容量为i时前j－1件物品的最优值；第二种情况为要第j件物品，则最优情况为背包容量为i-第j件物品体积时前j－1件物品的最优值加上第j件物品的值，这种情况要求i-第j件物品体积 >= 0。取两种情况里面较大的作为dp[i][j]的值。

    public int backPack(int m, int[] A) {
        if(m == 0 || A == null || A.length == 0){
            return 0;
        }

        int n = A.length;
        int[][] fillPack = new int[m + 1][n + 1];

        for(int i = 0; i <= m; i++){
            fillPack[i][0] = 0;
        }

        for(int j = 0; j <= n; j++){
            fillPack[0][j] = 0;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i - A[j - 1] >= 0){
//第二种情况为要第j件物品，则最优情况为背包容量为i-第j件物品体积时前j－1件物品的最优值加上第j件物品的值。
                    fillPack[i][j] = Math.max(fillPack[i][j - 1], fillPack[i - A[j - 1]][j - 1] + A[j - 1]);
                }else{//一种情况为不要第j件物品，则最优情况为背包容量为i时前j－1件物品的最优值；
                    fillPack[i][j] = fillPack[i][j - 1];
                }
            }
        }

        return fillPack[m][n];
    }

第二种方法dp[i][j]表示前i件物品能否填满容量为j的背包。分两种情况：一种情况为不要第i件物品，则dp[i][j]=dp[i-1][j]；第二种情况为要第j件物品，则dp[i][j] = dp[i-1][j - A[j]],不过这种情况要求j - A[j]>0。取两种情况里面较大的作为dp[i][j]的值。

    public int backPack(int m, int[] A) {
        boolean f[][] = new boolean[A.length + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j <= m; j++) {
                f[i + 1][j] = f[i][j];
                if (j >= A[i] && f[i][j - A[i]]) {
                    f[i + 1][j] = true;
                }
            } // for j
        } // for i

        for (int i = m; i >= 0; i--) {
            if (f[A.length][i]) {
                return i;
            }
        }
        return 0;
    }

https://zhengyang2015.gitbooks.io/lintcode/backpack_ii_125.html

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

Notice

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

Challenge

O(n x m) memory is acceptable, can you do it in O(m) memory?

和I类似。 value[i][j]表示容量为i的背包在前j件物品中能取的最大价值。分两种情况考虑：不要第j件物品，则value[i][j] = value[i][j-1]；要第j件物品，则value[i][j]=value[i－A［j］][j-1]+V[j]，这种情况要求i-A[j]>=0。取两种情况里面较大的作为value[i][j]的值。这种方法空间复杂度为O(n * m)。

    public int backPackII(int m, int[] A, int V[]) {
        if(m == 0 || A == null || A.length == 0){
            return 0;
        }

        int n = A.length;
        int[][] value = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i -A[j - 1] >= 0){
                    value[i][j] = Math.max(value[i][j - 1], value[i - A[j - 1]][j - 1] + V[j - 1]);
                }else{
                    value[i][j] = value[i][j - 1];
                }
            }
        }

        return value[m][n];
    }

第二种方法可以将空间复杂度优化到O(m)。f[j]表示背包容量为j时在前i件物品中能够选取的最大价值。到第i件物品时，考虑第i件物品装还是不装。背包容量j从最大的容量m开始依次递减遍历，只考虑更新背包容量大于A[i]的情况，即加上V[i]之后是否结果会更优，背包容量小于A[i]的情况不用考虑因为第i件物品根本装不进此时容量的背包。若结果更优，则更新此时的f[j]（即装第i件物品时情况更优），否则不变（即不装第i件物品时情况更优）。因为f会记录i之前所有的最优情况，因此只需要m空间即可。物品从0遍历到n－1，即可求出前n件物品的最优值。

space O(m)：

    public int backPackII(int m, int[] A, int V[]) {
        int[] f = new int[m + 1];

        for(int i = 0; i < n; i++){
            for(int j = m; j >= A[i]; j--){//\\
                if(f[j] < f[j - A[i]] + V[i]){
                    f[j] = f[j - A[i]] + V[i];
                }
            }
        }

        return f[m];
    }

其实第二种方法相当于使用滚动数组。因为状态函数为

value[i][j]=max(value[i－A［j］][j-1]+V[j], value[i][j-1])

可以看出只和j－1有关，因此保存两行信息就足够了。使用滚动数组必须逐行填写，因为在计算下一行的时候需要上一行的信息，像第一种方法中那样逐列填写就不行。

    public int backPackII(int m, int[] A, int V[]) {
        if(m == 0 || A == null || A.length == 0){
            return 0;
        }

        int n = A.length;
        int[][] value = new int[m + 1][2];

        for(int j = 1; j <= n; j++){
            for(int i = 1; i <= m; i++){
                if(i -A[j - 1] >= 0){
                    value[i][j % 2] = Math.max(value[i][(j - 1) % 2], value[i - A[j - 1]][(j - 1) % 2] + V[j - 1]);
                }else{
                    value[i][j % 2] = value[i][(j - 1) % 2];
                }
            }
        }
    }

Lintcode: Backpack II - neverlandly - 博客园
用子问题定义状态：即f[i][v]表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程便是： f[i][j] = max{f[i-1][j], j>=A[i-1]? f[i-1][j-A[i-1]]+V[i-1] : 0}

    public int backPackII(int m, int[] A, int V[]) {
 8         int[][] res = new int[A.length+1][m+1];
 9         res[0][0] = 0;
10         for (int i=1; i<=A.length; i++) {
11             for (int j=0; j<=m; j++) {
12                 if (j - A[i-1] < 0)
13                     res[i][j] = res[i-1][j];
14                 if (j - A[i-1] >= 0) {
15                     res[i][j] = Math.max(res[i-1][j], res[i-1][j-A[i-1]]+V[i-1]);
16                 }
17             }
18         }
20         return res[A.length][m];
21     }

Use one dimension array:

    public int backPackII(int m, int[] A, int V[]) {
        int[] d = new int[m+1];

        for (int i = 1; i <= A.length; i++) {
            for (int j = m; j >= 0; j--) {
                if (j == 0) {
                    d[j] = 0;
                } else {
                    if (A[i-1] <= j) {
                        d[j] = Math.max(d[j-A[i-1]]+V[i-1], d[j]);
                    }
                }
            }
        }
        return d[m];
    }

O(nm)

http://www.cnblogs.com/EdwardLiu/p/4269149.html

Given n items with size A[i], an integer m denotes the size of a backpack.

How full you can fill this backpack? 

Note
You can not divide any item into small pieces.

2D code:

7     public int backPack(int m, int[] A) {
 8         // write your code here
 9         boolean[][] res = new boolean[A.length+1][m+1];
10         res[0][0] = true;
11         for (int i=1; i<=A.length; i++) {
12             for (int j=0; j<=m; j++) {
13                 res[i][j] = res[i-1][j] || (j-A[i-1]>=0 && res[i-1][j-A[i-1]]);
14             }
15         }
16         for (int j=m; j>=0; j--) {
17             if (res[A.length][j]) return j;
18         }
19         return 0;
20     }

1D code:

7     public int backPack(int m, int[] A) {
 8         if (A.length==0) return 0;
 9         
10         int len = A.length;
11         boolean[] size = new boolean[m+1];
12         Arrays.fill(size,false);
13         size[0] = true;
14         for (int i=1;i<=len;i++)
15             for (int j=m;j>=0;j--){
16                 if (j-A[i-1]>=0 && size[j-A[i-1]])
17                     size[j] = size[j-A[i-1]];
18             }
19 
20         for (int i=m; i>=0;i--)
21             if (size[i]) return i;
22 
23         return 0;
24     }

Backpack III 440
https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html

Given n kind of items with size Ai and value Vi( each item has an infinite number available) and a backpack with size m. What's the maximum value can you put into the backpack?

Notice

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 15.

这道题和II的思想一样，f[j]表示容量为j的背包对前i件物品能取的最大值，其中物品可以重复选取。对物品从0遍历到n－1，每次只有比A[i]大的背包容量才有可能被更新。

和II不同的是，这道题物品可以重复选择，所以内层遍历j的时候从小到大遍历，这样物品可以重复选取。比如一开始在j的时候取了i，然后随着j的增大，在j'的时候又取了i，而恰好j = j' - A[i]，在这种情况下i就被重复选取。如果从大往小遍历则所有物品只能取一次，所以II中是从大往小遍历。

因此可以重复取元素则背包容量从小到大遍历，反之从大到小遍历。

    public int backPackIII(int[] A, int[] V, int m) {
        // Write your code here
        int[] f = new int[m + 1];

        for(int i = 0; i < A.length; i++){
            for(int j = A[i]; j <= m; j++){
            //对于当前物品i，若j从小到大的话，很可能在j之前的j-A[i]时已经放过第i件物品了，在j时再放就是重复放入；若j从大到小，则j之前的所有情况都没有更新过，不可能放过第i件物品，所以不会重复放入。
                if(f[j - A[i]] + V[i] > f[j]){
                    f[j] = f[j - A[i]] + V[i];
                }
            }
        }

        return f[m];
    }

Backpack IV 562
https://zhengyang2015.gitbooks.io/lintcode/backpack_iv_562.html

Given n items with size nums[i] which an integer array and all positive numbers, no duplicates. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.

Each item may be chosen unlimited number of times.

Example

Given candidate items [2,3,6,7] and target 7,

A solution set is:

[7]

[2, 2, 3]

return 2

这道题思路和III几乎一样，dp[j]表示背包容量为j时，对前i中物品来说能填满背包的方法数。当前元素为i时，背包容量大于等于nums[i]的才有可能被更新。此时，对于j容量的背包，其新的方法数为前i－1件物品能装满j容量背包的方法数（即不装第i件物品的方法数）＋前i-1件物品能装满j-nums[i]容量的背包的方法数（即装第i件物品的方法数）。这里状态方程只是把III中的max改成了+。所有求总共有多少种方法的题都可以从最大值问题变换max为+得到。因此，状态函数为：

dp[j] = dp[j] + dp[j - nums[i]] (右边的dp[j]表示上一行中（即i－1件物品）能装满j容量的方法数)

    public int backPackIV(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for(int i = 0; i < nums.length; i++){
            for(int j = nums[i]; j <= target; j++){
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[target];
    }

Backpack V 563
https://zhengyang2015.gitbooks.io/lintcode/backpack_v_563.html

Given n items with size nums[i] which an integer array and all positive numbers. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.

Each item may only be used once.

Example

Given candidate items [1,2,3,3,7] and target 7,

A solution set is:

[7]

[1, 3, 3]

return 2

这题和IV几乎一样, 不同的是元素只能取一次，因此内层遍历j的时候从大到小遍历（解释见III）。dp[j]表示背包容量为j时，对前i件物品且每件物品只能取一次的情况下能取的最大值。dp[0]解释一下：就是将容量为0的背包装满的方法，显然只有一种，就是什么都不装

    public int backPackV(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for(int i = 0; i < nums.length; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[target];
    }

https://zhengyang2015.gitbooks.io/lintcode/backpack_vi_564.html

Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Notice

The different sequences are counted as different combinations.

Example

Given nums = [1, 2, 4], target = 4

The possible combination ways are:

[1, 1, 1, 1]

[1, 1, 2]

[1, 2, 1]

[2, 1, 1]

[2, 2]

[4]

return 6

dp[j]表示背包容量为j时，数组nums能装满j的方法数量。

可以想到的方法是对于当前背包容量j，假设最后加入的元素为当前遍历的元素i，则将i元素最后加入的方法数量为dp[j - nums[i]]（此时要求j - nums[i] >= 0），将数组元素全部遍历当过i为止。其中，初始化dp[0]=1，表示数组元素将容量为0的背包装满的方法数为1（即什么元素都不取这一种方法）。

这道题并不难，但需要注意要和IV，V的区别。IV，V中的方法和元素位置有关系，元素的相对位置不能变化，不能先取后面的元素再取前面的元素，即相同元素组成的方法被视为一种方法（就算排列不同），其dp[j]的含义为前i件物品装满容量j的方法数，因此只和i之前的物品相关，而和i之后的物品无关。这道题则说明不同的顺序被认为是不同的方法，因此和元素位置无关，可以先取后面的元素再取前面的元素，即相同元素的不同排列被视为不同的方法，其dp[j]表示的是数组nums装满容量j的方法数，是和数组中所有元素有关。

之前几题能够用一维dp表示的本质其实是因为当前行的值只和上一行有关，因此用动态数组两行就行，如果直接在上一行更新当前行的状态则只需要一行即可，因此其本质就是还是二维dp。但是这道题真的是一维dp，即当前容量的填装数量只和之前容量填装的结果有关，只不过每次填装都要遍历整个nums数组来寻找相关的之前容量的状态，因此要用两重for循环。

    public int backPackVI(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for(int i = 1; i <= target; i++){
            for(int j = 0; j < nums.length; j++){
                if(i - nums[j] >= 0){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

Read full article from Lintcode: Backpack II - neverlandly - 博客园

Algorithms Forever ...: Largest sum of elements with no three consecutive

Maximum sum such that no two elements are adjacent - GeeksforGeeks

Lintcode: Backpack I,II,III,IV,V

Labels

Popular Posts