ORID43

objective1.3 Java project

day 1
https://www.udemy.com/course/complete-android-n-developer-course/learn/lecture/5689960#overview
准备把这门课上面的一个project做完，目标8月底之前完成

lintcode 92 背包问题

用什么算法？

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
Example
Example 1:
Input: [3,4,8,5], backpack size=10
Output: 9

Example 2:
Input: [2,3,5,7], backpack size=12
Output: 12

动归，背包型动归都要用背包的大小来作为dp[][] 的大小
为什么要二维数组呢？ 因为第一个也就是每行dp[i]代表的是你在A[i]当前这个重量中是否可以拿够总重量（如果改成拿到最大价值的物品，那么也可以改成int[][] dp）

代码实现

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

    int n = A.length;
    if (n == 0) {
        return 0;
    }
    boolean[][] f = new boolean[n + 1][m + 1]; 
    f[0][0] = true; //init, true for 0 weight
    for (int i = 1; i <= m; i++) {
        f[0][i] = false;
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if ( j >= A[i - 1]) {
                f[i][j] = f[i - 1][j] || f[i - 1][j - A[i - 1]]; //这句判断才是关键…… f[i - 1][j - A[i -1]] 实际上在检测如果当前包裹容量超过要拿的重量，你就看你上次
//那这个物品剩余的重量是否能够拿到，如果可以，那就设置成true，也就是说，你当前容量减去要拿重量为true，举个例子，[3,4,8,5]
// 你j为8的时候，j-8等于0，也就是最开始的true，那么就证明你能拿8这个重量，然后继续j++之后就等于9， 9 - 8 等于1，但是A这个数组里面没有1，所以是false，所以9拿不到。以此类推
            }
        }
      for (int i = m; i >= 0; i--) {
          if (f[n][i]) {
              return i; //就代表当前的重量能够拿到，而且取的是最大值(从大到小）。
          }
      }
      return 0; //就代表这个for loop里面没找到能够返回的重量，直接返回0 就行了。
    }
}