编写题解 1924: 蓝桥杯算法提高VIP-01背包

解题思路:

物品i    1    2    3    4    5    背包j    

1    0    3    3    3    3    背包体积一定要大于物品体积    

2    0    3    5    5    8    如果背包的体积大于物品的体积，那么就是可以装的下，就把上一层的值与上一层值+物品价值，对比；    

3    0    3    5    7    8    如果背包的体积小于物品的体积，那么就是装不下，就把上一层的数据给到这一层    

注意事项:

参考代码:

import java.util.Scanner;


public class Text08 {
    public static void main(String []args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();//物品的个数
        int m=scanner.nextInt();//背包的重量
        int []arr=new int[n+1];//物品的重量
        int []arr1=new int[n+1];//物品的价值
        for (int i = 1; i <=n; i++) {
            arr[i]=scanner.nextInt();
            arr1[i]=scanner.nextInt();
        }
        //现在的程序是，背包的容量不减，价值不加；
        
        //放在背包的物品是价值
        int [][] dp=new int[n+1][m+1];
        //控制物品重量
        for (int i = 1; i <=n; i++) {
            //控制背包
            for (int j = 1; j <=m; j++) {
                //背包小于物品的重量
                if (j>= arr[i]) {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-arr[i]]+arr1[i]);
                }
                else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }

}