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

解题思路: 

dp[i][j]表示面对第 i 个物品时，最大重量 j 的背包所拥有的最大价值

打表，找出状态转移方程：

if(j<w[i]){  //不拿
dp[i][j]=dp[i-1][j];
}else{   //拿或不拿
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}

参考代码:

方法一：二维dp表

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),m=sc.nextInt(); //物品个数、背包最大重量
		int[] w=new int[n+1];
		int[] v=new int[n+1];
		int[][] dp=new int[n+1][m+1];
		for(int i=1;i<n+1;i++){
			w[i]=sc.nextInt();
			v[i]=sc.nextInt();
		}
		for(int i=1;i<n+1;i++){ //第i个物品
			for(int j=1;j<m+1;j++){  //重量为j的背包
				if(j<w[i]){  //不拿
					dp[i][j]=dp[i-1][j];
				}else{   //拿或不拿
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); 
				}
			}
		}
		System.out.print(dp[n][m]);
	}
}

方法二：一维dp表

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),m=sc.nextInt(); //物品个数、背包最大重量
		int[] w=new int[n+1];
		int[] v=new int[n+1];
		int[] dp=new int[m+1];
		for(int i=1;i<n+1;i++){
			w[i]=sc.nextInt();
			v[i]=sc.nextInt();
		}
		for(int i=1;i<n+1;i++){ //第i个物品
			for(int j=m;j>=1;j--){  //重量为j的背包,要从后往前推，因为从前往后推会把上一条的dp[j-w[i]]记录给覆盖
				if(j>=w[i]){       //j<w[i]放不下就不拿不更新dp表，j>=w[i]放得下就更新dp表
					dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]);
				}
			}
		}
		System.out.print(dp[m]);
	}
}