8.9 动态规划简介及 01背包问题

本文主要是介绍8.9 动态规划简介及 01背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划简介：

01背包问题：对于每个物品只有选和不选两种情况（与上题不同之处：物体不可分）

代码：


import java.util.Arrays;
import java.util.Scanner;public class Main {/* */static int n;static int[] ws;static int[] vs;static int cnt=0;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)进行dfs，选择物品，使其满足W的限制下，总价值最大cnt = dfs(0,W);//从下标为0的物品开始搜索，当前可承重为WSystem.out.println(cnt);}//返回最大价值private static int dfs(int k, int w) {if(k==n) return 0;//选完所有物品，此时无物品可选if(w<=0) return 0;//当前承重小于等于0，即背包已满//（1）不选择当前物品int cnt1 = dfs(k+1,w);//(2)选择当前物品if(ws[k]<=w) {//当前物品可放入背包int cnt2 = vs[k]+dfs(k+1,w-ws[k]);//继续遍历下一个物品//（3）返回两种情况下最大价值return Math.max(cnt1,cnt2);}else {//背包已满，不可放return cnt1;}}
}

可发现圈出的部分重复求解了，对于这种重叠子问题，通过记忆型递归（带备忘录递归）解决该问题

即：通过数组将计算过的结果记录下来，下次遇到这种情况时，可直接使用该结果

例如：f(3,2), 可存储为：rec[物体下标2][背包容量2]=该情况下的总价值

（第一个下标范围是0~物体总数-1、第二个范围0~背包最大容量）

记忆型递归代码：


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[] ws;static int[] vs;static int cnt=0;static int[][] rem;//记忆数组。rem[i][j] 当前物品i，背包可承重j 所对应的最大价值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）初始化rem值为-1rem = new int[n][W+1]; //物品下标范围0~n-1、  可承重范围1~Wfor(int i=0;i<n;i++) {for(int j=0;j<=W;j++) {rem[i][j]=-1;}}//(3)进行dfs，选择物品，使其满足W的限制下，总价值最大cnt = dfs(0,W);//从下标为0的物品开始搜索，当前可承重为WSystem.out.println(cnt);}//返回最大价值private static int dfs(int k, int w) {if(k==n) return 0;//选完所有物品，此时无物品可选if(w<=0) return 0;//当前承重小于等于0，即背包已满//(1)计算之前先查询。   先查询在物品k，可承重w情况下，是否已有记录if(rem[k][w]>=0) {//已有记录，直接返回return rem[k][w];}//（2）没有改记录，进行计算。//（2.1）不选择当前物品int cnt1 = dfs(k+1,w);//(2.2)选择当前物品int cn=0;//记录当前情况下的最大价值if(ws[k]<=w) {//当前物品可放入背包int cnt2 = vs[k]+dfs(k+1,w-ws[k]);//继续遍历下一个物品//（3）返回两种情况下最大价值cn = Math.max(cnt1,cnt2);}else {//背包已满，不可放cn = cnt1;}//（3）计算之后做记录。rem[k][w]=cn;return cn;}
}