01背包

╰半夏微凉° 2022-06-08 09:37 190阅读 0赞

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。
> 
> 输入：  
> 第一行两个整数n，m，分别代表石头的个数和背包的体积  
> 接下来n行，每行有两个整数，整数之间以空格隔开，分别表示石头的价值和体积
> 
> 输出：  
> 输出包括一个整数，表示背包可以装下最大的价值

第一种方法：用二维数组d\[i\]\[j\]保存当背包容量为j时前i个石头的最大价值

import java.util.Scanner;
    /**
     * 01背包 二维数组
     * @author Rose
     *
     */
    public class Dongtaiguihua {
        static int[][] dp;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
    
            int n = in.nextInt();
            int m = in.nextInt();
    
            int[] value = new int[n+1];
            int[] weight = new int[n+1];
    
            for (int i = 1; i <= n; i++) {
                value[i] = in.nextInt();
                weight[i] = in.nextInt();
            }
    
            dp = new int[n+1][m+1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if(j >= weight[i])
                        dp[i][j] = Math.max(dp[i-1][j-weight[i]]+value[i], dp[i-1][j]);
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
            System.out.println(dp[n][m]);
        }
    
    }

第一种算法造成一定的空间浪费，因为在遍历第i层时，程序中只需要第i-1层的数据，i-1层之前的不再考虑，所以我们可以用两个一维数组来存储当前层和上一层的最大价值，此时j的遍历是从m到1  
第二种方法：一维数组

import java.util.Scanner;
    
    /**
     * 01背包 一维数组
     * @author Rose
     *
     */
    public class Dongtaiguihua1 {
        static int[] dp;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[] value = new int[n+1];
            int[] weight = new int[n+1];
    
            for (int i = 1; i <= n; i++) {
                value[i] = in.nextInt();
                weight[i] = in.nextInt();
            }
            dp = new int[m+1];
            for (int i = 1; i <= n; i++) {
                for (int j = m; j >= 1; j--) {
                    if(j >= weight[i])
                        dp[j] = Math.max(dp[j-weight[i]]+value[i], dp[j]);
                }
            }
            System.out.println(dp[m]);
        }
    }