01背包,从简单递归到递归记忆化搜索到动态规划

ゝ一纸荒年。 2024-03-26 17:45 113阅读 0赞

[原题链接][Link 1]

[左神(左程云)视频讲解][Link 2]

### 递归版 ###

递归考虑思路,从第一块物品开始我们根据当前背包剩余的容量有两种选择

第一种是选择当前物品加入背包

第二种是不选择当前物品加入背包

1.当我们的容量不足以装下当前物品时,我们只有第一种选择,即抛弃当前物品,继续判断下一个物品

if (restV - vi[index] < 0) {
 return digui(restV, index + 1);
 }
 //restV表示剩余容量,index表示当前正在处理第几个物品

2.当我们的容量足以当下当前物品时,我们就有两种选择了,即选择当前物品或抛弃当前物品,并返回两种选择的最大值

return Math.max(digui(restV - vi[index], index + 1) + wi[index],
                    digui(restV, index + 1));

3.那么我们的递归要如何结束呢,显然当我们选完所有物品后递归结束

if (index == vi.length) {
                return 0;
    }

4.最后的完整代码

注意 N物品数量

V最大容积

vi\[\]物品重量数组

wi\[\]物品价值数组

以上都是全局变量

import java.util.Scanner;
 public class Main {
 public static int N, V;
 public static int vi[];
 public static int wi[];
 public static Scanner sc = new Scanner(System.in);
 // 返回的值为价值
 public static int digui(int restV, int index) {
 //递归出口,选完所有物品
 if (index == vi.length) {
 return 0;
 }
 // 如果当前的物品的容量大于剩余背包的容量,则不可能加入
 if (restV - vi[index] < 0) {
 return digui(restV, index + 1);
 }
 // 返回加入与不加入的最大值
 return Math.max(digui(restV - vi[index], index + 1) + wi[index],
 digui(restV, index + 1));
 } 
 public static void main(String[] args) {
 int N = sc.nextInt();
 int V = sc.nextInt();
 vi = new int[N];
 wi = new int[N];
 for (int i = 0; i < N; i++) {
 vi[i] = sc.nextInt();
 wi[i] = sc.nextInt();
 }
 System.out.println(digui(V, 0));
 }
 }

### 记忆化搜索版 ###

让我们考虑观察该递归函数

int digui(int restV, int index);

我们发现该函数返回一个整数,参数分别是restV(剩余容量)和index(当前正在处理的物品)

如果我们将函数看成一种映射,也就是说当restV和index固定的时候,返回值也就随之固定了

也就是说,一旦restV和index固定,函数的结果就实际上已经确定了

于是我们可以用一个二位数组dp\[\]\[\]来记录参数是restV和index时函数返回的结果

于是我们可以将递归函数改成下面的样子

dp[][] = {-1} //dp初始化为-1 
 public static int memory(int restV, int index) {
 if (dp[restV][index] != -1) {
 return dp[restV][index];
 }
 if (index == vi.length) {
 dp[restV][index] = 0;
 return dp[restV][index];
 }
 // 如果当前的物品的价值大于整个背包的容量,则不可能加入
 if (restV - vi[index] < 0) {
 dp[restV][index] = digui(restV, index + 1);
 return dp[restV][index];
 }
 // 返回加入与不加入的最大值
 dp[restV][index] = Math.max(digui(restV - vi[index], index + 1) + wi[index],
 digui(restV, index + 1));
 return dp[restV][index];
 }

### 动态规划版 ###

让我们观察记忆化版

我们发现当index == vi.length时其实函数的返回结果就已经确定了是0

于是我们可以直接赋值dp\[restV\]\[vi.length\] = 0;

这就是dp数组的初态

index

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;"> restV</td> 
 <td style="width:99px;vertical-align:top;height:52px;">0</td> 
 <td style="width:100px;vertical-align:top;height:52px;">1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">2</td> 
 <td style="width:68px;vertical-align:top;height:52px;">.....</td> 
 <td style="width:121px;vertical-align:top;height:52px;">vi.length-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">vi.length</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 <td style="width:99px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">1</td> 
 <td style="width:99px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">2</td> 
 <td style="width:99px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">...</td> 
 <td style="width:99px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">V-1</td> 
 <td style="width:99px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">V</td> 
 <td style="width:99px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 </tbody> 
</table>

从右往左看,并观察函数

if (restV - vi[index] < 0) {
 dp[restV][index] = digui(restV, index + 1);
 return dp[restV][index];
 }
 // 返回加入与不加入的最大值
 dp[restV][index] = Math.max(digui(restV - vi[index], index + 1) + wi[index],
 digui(restV, index + 1));
 return dp[restV][index];

我们发现vi.length - 1的值是由vi.length的值得来的

如果能装下第vi.length-1的物品那么返回值就是max(dp\[vi.length\]\[restV\],0) = dp\[vi.length\]\[restV\]

所以我们就得到了下面的dp状态

index 如果剩余的容量能装下wi\[length\],就填wi

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;"> restV</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 <td style="width:100px;vertical-align:top;height:52px;">1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">2</td> 
 <td style="width:68px;vertical-align:top;height:52px;">.....</td> 
 <td style="width:121px;vertical-align:top;height:52px;">vi.length-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">vi.length</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">0</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">0</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">2</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">0</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">...</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">...</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">V-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">wi[length]</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 <tr> 
 <td style="width:100px;vertical-align:top;height:52px;">V</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:100px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:68px;vertical-align:top;height:52px;">-1</td> 
 <td style="width:121px;vertical-align:top;height:52px;">wi[length]</td> 
 <td style="width:100px;vertical-align:top;height:52px;">0</td> 
 </tr> 
 </tbody> 
</table>

然后表继续从右往左填,直到填完所有的表

最后返回dp\[V\]\[0\]的值即可

完整代码如下

import java.util.Scanner;
 
 public class Main {
 public static int N, V;
 public static int vi[];
 public static int wi[];
 public static Scanner sc = new Scanner(System.in);
 public static int dp[][];
 
 // 返回的值为价值
 public static int digui(int restV, int index) {
 if (index == vi.length) {
 return 0;
 }
 // 如果当前的物品的价值大于整个背包的容量,则不可能加入
 if (restV - vi[index] < 0) {
 return digui(restV, index + 1);
 }
 // 返回加入与不加入的最大值
 return Math.max(digui(restV - vi[index], index + 1) + wi[index],
 digui(restV, index + 1));
 }
 
 // 返回的值为价值
 public static int memory(int restV, int index) {
 if (dp[restV][index] != -1) {
 return dp[restV][index];
 }
 if (index == vi.length) {
 dp[restV][index] = 0;
 return dp[restV][index];
 }
 // 如果当前的物品的价值大于整个背包的容量,则不可能加入
 if (restV - vi[index] < 0) {
 dp[restV][index] = digui(restV, index + 1);
 return dp[restV][index];
 }
 // 返回加入与不加入的最大值
 dp[restV][index] = Math.max(digui(restV - vi[index], index + 1) + wi[index],
 digui(restV, index + 1));
 return dp[restV][index];
 }
 
 public static void main(String[] args) {
 int N = sc.nextInt();
 int V = sc.nextInt();
 vi = new int[N];
 wi = new int[N];
 dp = new int[V + 1][N + 1];
 for (int restV = 0; restV < V + 1; restV++) {
 for (int index = 0; index < N + 1; index++) {
 dp[restV][index] = -1;
 }
 }
 for (int i = 0; i < N; i++) {
 vi[i] = sc.nextInt();
 wi[i] = sc.nextInt();
 }
 //System.out.println(digui(V, 0));
 // System.out.println(memory(V, 0));
 for (int restV = 0; restV < V + 1; restV++) {
 for (int index = 0; index < N + 1; index++) {
 dp[restV][index] = -1;
 }
 }
 for (int restV = 0; restV < V; restV++) {
 dp[restV][vi.length] = 0;
 }
 for (int index = N - 1; index >= 0; index--) {
 for (int restV = 0; restV <= V; restV++) {
 if (restV - vi[index] < 0) {
 dp[restV][index] = dp[restV][index + 1];
 
 } else {
 dp[restV][index] = Math.max(dp[restV - vi[index]][index + 1] + wi[index],
 dp[restV][index + 1]);
 }
 
 }
 }
 
 System.out.println(dp[V][0]);
 
 }
 }

[Link 1]: https://www.acwing.com/problem/content/2/
[Link 2]: https://www.bilibili.com/video/BV13g41157hK?p=17&vd_source=8651deb552ff255ac3dc29dc9a2f40ec