解题思路:
举个例子,假设我们有三个物品 A、B、C,以及背包容量分别为 5。在遍历物品 A 时,我们要计算背包容量为 5 时的最大价值,同时也要计算背包容量为 4、3、2、1、0 时的最大价值。然后在遍历物品 B 时,同样需要计算所有这些容量下的最大价值。这样一直进行下去,直到遍历完所有的物品。
注意事项:
参考代码:
import java.util.*; public class Main { public static void main(String args []) { Scanner sc = new Scanner(System.in); int n,m; int i,j; n= sc.nextInt(); m=sc.nextInt(); int[] dp = new int[n+1];//最大价值 int[] v = new int[m+1];//表示价值 int[] w = new int [m+1];//表示权重(权重=价值*重要因子) for(i=1;i <= m;i++) { w[i] = sc.nextInt(); v[i] = sc.nextInt(); v[i]*=w[i];//权重=价值*重要因子 } for(i=1;i = 0;j--) { if(j >= w[i]) dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);//动态方程 } System.out.println(dp[n]); } }
0.0分
0 人评分