lintcoe 92 · Backpack

https://www.lintcode.com/problem/92/

紀錄重量是否可裝滿？ boolean, 所以最後還要倒著去看重量(由大到小, find true

dp[ith item] [ total weight] = boolean

time: O(m*n)

space: O(m*n)

/*
m denotes the size of a backpack

dp[i][j] = can pre num i to fit sum = j or not, use boolean

if (j >= A[i-1]) {
    dp[i][j] = dp[i-1][j] || dp[i-1][j - A[i-1]];
} else {
    dp[i][j] = dp[i-1][j];
}
*/

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        int n = A.length;
        boolean[][] dp = new boolean[n+1][m+1]; // item from 0~n, size from 0~m

        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j >= A[i-1]) {
                    // choose or not choose
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - A[i-1]];
                } else {
                    // j < A[i-1], size of a backpack j < item size, can't choose
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        // find the max weight which status is true(can put in pack)
        // from weight m to find true status
        for (int i = m; i >= 0; i--) {
            if (dp[n][i]) {
                return i;
            }
        }
        return -1;
    }
}

or 紀錄重量

/*
m denotes the size of a backpack

dp[i][j] = select pre num i  <= j (sum), dp[i][j] is the sum 

*/
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int n = A.length;
        int dp[][] = new int[n+1][m+1];

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

        return dp[n][m];
    }
}

python

init dp [ [0]*col size for _ in range(row size) ]

for, if , else have :

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @return: The maximum size
    """
    def backPack(self, m, A):
        n = len(A)
        dp = [[0]*(m+1) for _ in range(n+1)]

        for i in range(1, n+1):
            for j in range(0, m+1):
                if (j >= A[i-1]):
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1])
                else:
                    dp[i][j] = dp[i-1][j]

        return dp[n][m]