背包问题之有依赖的背包问题

package com.zhang.reflection.面试.算法模版.背包问题模版;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 有 N 组物品和一个容量是 V 的背包。
 *
 * 每组物品有若干个，同一组内的物品最多只能选一个。
 * 每件物品的体积是 v_ij，价值是 w_ij，其中 i 是组号，j 是组内编号。
 *
 * 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
 * 输出最大价值。
 *
 * 第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
 * 接下来有 N 组数据：
 * 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
 * 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
 *  输入
 *  3 5
 *  2
 *  1 2
 *  2 4
 *  1
 *  3 4
 *  1
 *  4 5
 *  输出
 *  8
 */
public class 分组背包 {
    //优化，使用一维dp数组
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        int N=Integer.parseInt(split[0]);
        int V=Integer.parseInt(split[1]);
        int[] dp=new int[V+1];
        int[] v=new int[105];
        int[] w=new int[105];

        for(int i=1;i<=N;i++) {
            String[] s = br.readLine().split(" ");
            int M=Integer.parseInt(s[0]);  //输入几组数据
            for(int j=0;j<M;j++) {
                String[] ss = br.readLine().split(" ");
                v[j]= Integer.parseInt(ss[0]);
                w[j]= Integer.parseInt(ss[1]);
            }
            //从V开始往前遍历 有限个数
            for(int j=V;j>=0;j--) {
                for(int k=0;k<M;k++) { //遍历每一个组
                    if(j>=v[k]) {
                        dp[j]=Math.max(dp[j], dp[j-v[k]]+w[k]);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}
//非优化，使用二维dp数组
//import java.io.*;
//import java.lang.*;
//
//public class 分组背包问题_二维DP{
//
//    static int n = 0, m = 0, N = 110;
//    static int[][] f = new int[N][N];
//    static int[][] v= new int[N][N], w = new int[N][N];
//    static int[] s = new int[N];
//
//    public static void main(String[] args)throws Exception{
//        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
//        String[] params = buf.readLine().split(" ");
//        n = Integer.valueOf(params[0]);
//        m = Integer.valueOf(params[1]);
//
//        for(int i = 1; i <= n; ++i){
//            int cnt = Integer.valueOf(buf.readLine());
//            s[i] = cnt;//记录每组的数量
//            for(int j = 1; j <= cnt; ++j){
//                String[] info = buf.readLine().split(" ");
//                int a = Integer.valueOf(info[0]);
//                int b = Integer.valueOf(info[1]);
//                v[i][j] = a;
//                w[i][j] = b;
//            }
//        }
//
//        for(int i = 1; i <= n; ++i){
//            for(int j = 0; j <= m; ++j){
//                f[i][j] = f[i - 1][j]; //不选
//                //枚举当前组中全部的数,选不选第x个
//                for(int x = 0; x <= s[i]; ++x){
//                    if(v[i][x] <= j)
//                        //最终还是转化为01背包问题，选不选第x个的问题
//                        f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i][x]] + w[i][x]);
//                }
//            }
//        }
//        System.out.print(f[n][m]);
//    }
//}