动态规划有依赖的背包问题

- 日理万妓 2021-10-01 12:22 276阅读 0赞

![5057999-519124182d48783c.png][]

![5057999-cb79cb0b358e5015.png][]

![5057999-52e1f334d18930fb.png][]

public class Main {
        public static int getMaxValue(int[] val,int[] weight,int[] q,int n,int w){
            int[][]dp= new int[n+1][w+1];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=w;j++){
                    if(q[i-1]==0){
                        if(weight[i-1]<=j)
                             dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j- weight[i - 1]]+ val[i - 1]);
                        else{
                            if (weight[i - 1] + weight[q[i - 1]] <= j) //附件的话 加上主件一起算  
                                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j- weight[i - 1]]+ val[i - 1]);
                        }
                    }
                }
            }
            return dp[n][w];
        }
        
        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            while (input.hasNextInt()) {
                int n = input.nextInt(); // 总钱数
                int m = input.nextInt(); // 商品个数
                int[] p = new int[m];
                int[] v = new int[m];
                int[] q = new int[m];
                for (int i = 0; i < m; i++) {
                    p[i] = input.nextInt();// 价格
                    v[i] = input.nextInt() * p[i]; // 价值 
                    q[i] = input.nextInt();// 主or附件            
                }
                System.out.println(getMaxValue(v, p, q, m, n));
                }
        }
    }

[5057999-519124182d48783c.png]: /images/20210811/86649afb2f604ac1838eec24d4a0e5f3.png
[5057999-cb79cb0b358e5015.png]: /images/20210811/a0629a349c574b9bafa3697340521f5f.png
[5057999-52e1f334d18930fb.png]: /images/20210811/88bcc8aa45f043e5b6bdc110aa471eef.png