蓝桥杯算法提高VIP-01背包-详细解释(重在理解)

解题思路:

第一步:先利用表格梳理思路

第二步:进行题目分析

  当物品重量大于背包容量时则说明背包装不下该物品,因此此时背包中总价值为没装当前物品时的价值:dp[i][j]=dp[i-1][j];当物品重量小于背包容量时则说明背包可以装下该物品,因此此时背包中的总价值应该为:dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-物品重量]+物品价值);

  此时的 dp[i-1][j-物品重量]+物品价值 是为了得出没装该物品之前的总价值加上当前物品价值之和;dp[i-1][j] 是为了找出装完上一个物品之后背包的总价值.

第三步:进行初步代码编写

参考代码:

一:常规二维数组写法

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();// 物品数量
		int b = scanner.nextInt();// 背包容量
		int[][]dp=new int[a+5][b+5];
		for (int i = 1; i <=a; i++) {
			int m=scanner.nextInt();//物品重量
			int n=scanner.nextInt();//物品价值
			for (int j = b; j >=1; j--) {
				if (j>=m) {
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-m]+n);
				}
				else {
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		System.out.println(dp[a][b]);
	}

}

二,简化代码后的一维数组写法

import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int a=scanner.nextInt();
		int b=scanner.nextInt();
		int abs[]=new int[b+5];
		for (int i = 1; i <=a; i++) {
			int m=scanner.nextInt();//体积
			int n=scanner.nextInt();//价值
			for (int j = b; j >=m; j--) {
				abs[j]=Math.max(abs[j], abs[j-m]+n);
			}
		}
		System.out.println(abs[b]);
	}

}