背包九讲Java版本

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> 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<Integer>[] v, List<Integer>[] 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];
    }


}