本文主要是介绍8.10 动态规划例题---01背包问题之dp(动态规划)解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分析：从第一行开始从左向右查找
对于物品3，容量4
要该物品：f(3,4) = 物品价值+f(物品3的上一个物品2，容量4-物品重量)；
不要该物品：f(3,4) = f(物品3的上一个物品，容量4)
最后取max(要f，不要f)
代码：
import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：（1）计算之前先查询记忆数组rem中是否已存在改记录* （1.1）如果存在，直接将该结果返回* （1.2）如果不存在，再计算* 并将计算结果存到rem数组中，再返回结果* 测试记录：
4
5
2 1 3 2
3 2 4 2*/static int n;//物品数static int W;//背包的容量限制static int[] ws;//每个物品的重量static int[] vs;//每个物品的价值static int[][] dp;//动态规划表（记录每个物品在每种容量下的总价值）public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);n = sc.nextInt();int W = sc.nextInt();ws = new int[n];vs = new int[n];for(int i=0;i<n;i++) {//输入每个物品重量ws[i]=sc.nextInt();}for(int i=0;i<n;i++) {//输入每个物品价值vs[i]=sc.nextInt();}//(2)初始化dp表dp = new int[n][W+1]; //物品编号0~n-1 、容量编号0~W//初始化第一行（物品0，在容量0~W下的价值）for(int i=0;i<=W;i++) {//i:背包容量if(ws[0]<=i) {//物品0的重量<背包容量i，选择物品0dp[0][i]=vs[0];//记录选择物品0后的价值}else {//容量不足，不选物品0dp[0][i]=0;}}//(3)依次遍历剩余的物品1~n-1for(int i=1;i<n;i++) {//物品ifor(int j=0;j<=W;j++) {//背包容量jint vv=0;//记录当前情况下的最大价值if(ws[i]<=j) {//背包容量足够int v1 = vs[i]+dp[i-1][j-ws[i]];//选择物品i。当前价值 = 物品i的价值 + 上一个物品i-1 在容量j-ws[i]的价值int v2 = dp[i-1][j]; //不选物品i。当前价值=上一个物品i-1在容量j下的价值vv=Math.max(v1, v2);}else {//背包容量不足vv=dp[i-1][j];//即不选物品i}dp[i][j]=vv;}}//(4)最后获取物品n-1，容量W下的最大价值System.out.println(dp[n-1][W]);}
}
这篇关于8.10 动态规划例题---01背包问题之dp(动态规划)解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
