add lintcode backpack

yi-yun · yi-yun · commit dcc0a87f243a · 2019-07-18T23:17:16.000+08:00
diff --git a/java_test/src/main/java/com/yiyun/ArrayToMap.java b/java_test/src/main/java/com/yiyun/ArrayToMap.java
@@ -0,0 +1,33 @@
+package com.yiyun;
+
+import org.junit.Test;
+
+import java.util.Map;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+/**
+ * @class: ArrayToMap
+ * @description: 将两个数组映射成 HashMap
+ * @author: yi-yun
+ * @create: 2019-07-18 21:21
+ **/
+public class ArrayToMap {
+    @Test
+    public void fun1() {
+        String[] keys = new String[]{"one", "two", "three"};
+        Integer[] values = new Integer[]{1, 2, 3};
+        Map<String, Integer> map = IntStream.range(0, keys.length).boxed().collect(
+            Collectors.toMap(i -> keys[i], i -> values[i])
+        );
+    }
+
+    @Test
+    public void fun2() {
+        String[] keys = new String[]{"one", "two", "three", "one"};
+        Integer[] values = new Integer[]{1, 2, 3, 4};
+        Map<String, Integer> map = IntStream.range(0, keys.length).boxed().collect(
+            Collectors.toMap(i -> keys[i], i -> values[i])
+        );
+    }
+}
diff --git a/myoffer/src/main/java/algorithm/dp/_1_ZeroOnePack.java b/myoffer/src/main/java/algorithm/dp/_1_ZeroOnePack.java
@@ -132,10 +132,10 @@ public void packOptimizationTest(int[] weight, int[] values, int n, int w) {
         }
         for (int i = 1; i < n; i++) {
             for (int j = w - weight[i]; j >= 0; j--) {
-                int v = states[j] + values[i];
-                if (v > states[j + weight[i]]) {
-                    states[j + weight[i]] = v;
-                }
+                    int v = states[j] + values[i];
+                    if (v > states[j + weight[i]]) {
+                        states[j + weight[i]] = v;
+                    }
             }
         }
     }
diff --git a/myoffer/src/main/java/lintcode/_125_backpack2.java b/myoffer/src/main/java/lintcode/_125_backpack2.java
@@ -0,0 +1,82 @@
+package lintcode;
+
+import org.junit.Test;
+
+/**
+ * @class: _125_backpack2
+ * @description: 背包问题2
+ * @author: yi-yun
+ * @create: 2019-07-18 22:14
+ **/
+public class _125_backpack2 {
+    /**
+     * @param m: An integer m denotes the size of a backpack
+     * @param A: Given n items with size A[i]
+     * @param V: Given n items with value V[i]
+     * @return: The maximum value
+     */
+    //恰好装满
+    public int backPackII(int m, int[] A, int[] V) {
+        // write your code here
+        int n = A.length;
+        int[] states = new int[m + 1];
+        for (int i = 0; i < m + 1; i++) {
+            states[i] = Integer.MIN_VALUE;
+        }
+        states[0] = 0;
+        if (A[0] <= m) {
+            states[A[0]] = V[0];
+        }
+        for (int i = 1; i < n; i++) {
+            for (int j = m - A[i]; j >= 0; j--) {
+                if (states[j] >= 0) {
+                    states[j + A[i]] = Integer.max(states[j] + V[i], states[j + A[i]]);
+                }
+            }
+        }
+        int res = Integer.MIN_VALUE;
+        for (int i = m; i >= 0; i--) {
+            res = Integer.max(res, states[i]);
+        }
+        return res;
+    }
+
+    //尽量装满 m 最大重量  A 重量数组    V 价值的数组
+    public int backPackII2(int m, int[] A, int[] V) {
+        // write your code here
+        int n = A.length;
+        int[] states = new int[m + 1];
+        for (int i = 0; i < m + 1; i++) {
+            states[i] = 0;
+        }
+        if (A[0] <= m) {
+            states[A[0]] = V[0];
+        }
+        for (int i = 1; i < n; i++) {
+            for (int j = m - A[i]; j >= 0; j--) {
+                states[j + A[i]] = Integer.max(states[j] + V[i], states[j + A[i]]);
+            }
+        }
+        return states[m];
+    }
+
+
+    @Test
+    public void fun1() {
+        backPackII(10, new int[]{2, 3, 5, 7}, new int[]{1, 5, 2, 4});
+    }
+
+    @Test
+    public void fun2() {
+        backPackII2(200,
+            new int[]{79, 58, 86, 11, 28, 62, 15, 68},
+            new int[]{83, 14, 54, 79, 72, 52, 48, 62});
+    }
+
+    @Test
+    public void fun3() {
+        backPackII(10,
+            new int[]{2, 3, 8},
+            new int[]{2, 5, 8});
+    }
+}
diff --git a/myoffer/src/main/java/lintcode/_92_backpack.java b/myoffer/src/main/java/lintcode/_92_backpack.java
@@ -0,0 +1,41 @@
+package lintcode;
+
+import org.junit.Test;
+
+/**
+ * @class: _92_backpack
+ * @description: 01背包，尽量装满
+ * @author: yi-yun
+ * @create: 2019-07-18 21:55
+ **/
+public class _92_backpack {
+    /**
+     * @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[] states = new int[m + 1];
+        if (A[0] <= m) {
+            states[A[0]] = 1;
+        }
+        for (int i = 0; i < n; i++) {
+            for (int j = m - A[i]; j >= 0; j--) {
+                states[A[i] + j] = Math.max(states[A[i] + j], states[j] + A[i]);
+            }
+        }
+        return states[m];
+    }
+
+    @Test
+    public void fun1() {
+        backPack(10, new int[]{3, 4, 8, 5});
+    }
+
+    @Test
+    public void fun2() {
+        backPack(12, new int[]{2, 3, 5, 7});
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -132,10 +132,10 @@ public void packOptimizationTest(int[] weight, int[] values, int n, int w) {`
`132`	`132`	`}`
`133`	`133`	`for (int i = 1; i < n; i++) {`
`134`	`134`	`for (int j = w - weight[i]; j >= 0; j--) {`
`135`		`- int v = states[j] + values[i];`
`136`		`- if (v > states[j + weight[i]]) {`
`137`		`- states[j + weight[i]] = v;`
`138`		`- }`
	`135`	`+ int v = states[j] + values[i];`
	`136`	`+ if (v > states[j + weight[i]]) {`
	`137`	`+ states[j + weight[i]] = v;`
	`138`	`+ }`
`139`	`139`	`}`
`140`	`140`	`}`
`141`	`141`	`}`