package dp;



import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;



/** * 背包九讲 * * @ProjectName: algorithm * @Package: dp * @Description: TODO * @Author: bipa * @Date: 2022/1/8 8:00 */

public class Pack { 

   



    /** * 01背包（每样物品的数量为一个） * * @param n 物品样数 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @return 总体积不超过m的最大价值 */

    public static int pack01(int n, int m, int[] v, int[] w) { 

   

        int[] dp = new int[m + 1];

        for (int i = 0; i < n; i++) { 

   

            for (int j = m; j >= v[i]; j--) { 

   

                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);

            }

        }

        return dp[m];

    }



    /** * 01背包方案数 * * @param n 物品数量 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @param mod 10^9 + 7 * @return 最优选法的方案数 */

    public static int getNumber(int n, int m, int[] v, int[] w, int mod) { 

   

        int[] dp = new int[m + 1], num = new int[m + 1];

        Arrays.fill(dp, Integer.MIN_VALUE);

        num[0] = 1;

        dp[0] = 0;

        for (int i = 0; i < n; i++) { 

   

            for (int j = m; j >= v[i]; j--) { 

   

                int temp = Math.max(dp[j], dp[j - v[i]] + w[i]);

                int sum = 0;

                if (temp == dp[j]) { 

   

                    sum += num[j];

                }

                if (temp == dp[j - v[i]] + w[i]) { 

   

                    sum += num[j - v[i]];

                }

                if (sum >= mod) { 

   

                    sum -= mod;

                }

                dp[j] = temp;

                num[j] = sum;

            }

        }

        int max = 0;

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

   

            max = Math.max(max, dp[i]);

        }

        int res = 0;

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

   

            if (max == dp[i]) { 

   

                res += num[i];

                if (res >= mod) { 

   

                    res -= mod;

                }

            }

        }

        return res;

    }



    /** * 01背包具体方案 * * @param n 物品数量 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @param link 连接符 * @return 最优选法的具体方案 */

    public static String getPath(int n, int m, int[] v, int[] w, String link) { 

   

        int[][] dp = new int[n + 1][m + 1];

        for (int i = n - 1; i >= 0; i--) { 

   

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

   

                dp[i][j] = dp[i + 1][j];

                if (j >= v[i]) { 

   

                    dp[i][j] = Math.max(dp[i][j], dp[i+1][j - v[i]] + w[i]);

                }

            }

        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) { 

   

            if (dp[i][m] == dp[i+1][m- v[i]] + w[i]) { 

   

                sb.append(link).append(i);

                m -= v[i];

            }

        }

        return sb.substring(1);

    }



    /** * 完全背包（每样物品的数量无限制） * * @param n 物品样数 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @return 总体积不超过m的最大价值 */

    public static int packComplete(int n, int m, int[] v, int[] w) { 

   

        int[] dp = new int[m + 1];

        for (int i = 0; i < n; i++) { 

   

            for (int j = v[i]; j <= m; j++) { 

   

                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);

            }

        }

        return dp[m];

    }



    /** * 多重背包（每样物品的数量为s） * * @param n 物品样数 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @param s 每样物品的数量 * @return 总体积不超过m的最大价值 */

    public static int packMultiple(int n, int m, int[] v, int[] w, int[] s) { 

   

        int[] dp_I = new int[m + 1];

        for (int i = 0; i < n; i++) { 

   

            for (int j = m; j >= v[i]; j--) { 

   

                for (int k = 1; k <= s[i] && k * v[i] <= j; k++) { 

   

                    dp_I[j] = Math.max(dp_I[j], dp_I[j - k * v[i]] + k * w[i]);

                }

            }

        }

        /** * 二进制优化，将每样物品的数量进行二进制拆分 */

        int[] dp_II = new int[m + 1];

        class Goods { 

   

            int v; // 体积

            int w; // 价值



            Goods(int v, int w) { 

   

                this.v = v;

                this.w = w;

            }

        }

        List goods = new ArrayList<>();

        for (int i = 0; i < n; i++) { 

   

            int k = s[i];

            for (int j = 1; j <= k; j *= 2) { 

   

                k -= j;

                goods.add(new Goods(j * v[i], j * w[i]));

            }

            if (k > 0) { 

   

                goods.add(new Goods(k * v[i], k * w[i]));

            }

        }

        for (Goods g : goods) { 

   

            for (int i = m; i >= g.v; i--) { 

   

                dp_II[i] = Math.max(dp_II[i], dp_II[i - g.v] + g.w);

            }

        }

        return dp_I[m];

    }



    /** * 二维费用背包 * * @param n 物品样数 * @param V 背包体积 * @param M 背包承受重量 * @param v 物品体积 * @param m 物品质量 * @param w 物品价值 * @return 总体积不超过V，总质量不超过M的最大价值 */

    public static int packTwo(int n, int V, int M, int[] v, int[] m, int[] w) { 

   

        int[][] dp = new int[V + 1][M + 1];

        for (int i = 0; i < n; i++) { 

   

            for (int j = V; j >= v[i]; j--) { 

   

                for (int k = M; k >= m[i]; k--) { 

   

                    dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);

                }

            }

        }

        return dp[V][M];

    }



    /** * 分组背包（每组物品最多选一个） * * @param n 组的数量 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @return 总体积不超过m的最大价值 */

    public static int packGroup(int n, int m, List[] v, List[] w) { 

   

        int[] dp = new int[m + 1];

        for (int i = 0; i < n; i++) { 

   

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

   

                for (int k = 0; k < v[i].size(); k++) { 

   

                    if (j >= v[i].get(k)) { 

   

                        dp[j] = Math.max(dp[j], dp[j - v[i].get(k)] + w[i].get(k));

                    }

                }

            }

        }

        return dp[m];

    }





}