背包问题

点击图片进入主页
不轻言放弃,年轻就是要拼搏 ~ ~ 本就是一无所有,又害怕失去什么?

01 背包问题

1. 前言

有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

初看觉得题目有点点小简单,只用把价值最大的物品放入进去背包里面,总价值也就最大了。但是仔细斟酌后发现!事情并没那么简单。
原因如下:

  • 是否有空间去装这个价值连城的物品
  • 舍去这个价值最大的物品,用腾出来的空间,换取更多价值低的物品。

于是乎,解题关键也就产生了: 对于一个物品,是否要取它,放入包包里

2. 公式推导

有了解题关键思想

对于一个物品,是否要取它,放入包包里

首先我们可以得到如下条件:

  • 用数组F[N][W]存储 有N件物品 ,背包空间是W时,能产生最大的价值
  • 第N件物品的价值nV
  • 第N件物品的体积nW

情况一

当nW>W的时候,说明背包根本放不下第N件物品,所以公式1:
F[N][W]=F[N-1][W]

情况二

当nW<W的时候,说明此时背包能放下第N件物品,但是存在一个问题,到底是放下N物品总价值高呢?还是不放它,换取空间存其他物品呢?所以公式2:
F[N][W]=Math.Max(F[N-1][W-nW]+nV,F[N-1][W])

3. 代码解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Map;

/**
* Demo class
*
* @author HengruiLiao
* @date 2019/4/19
*/
@SuppressWarnings("ALL")
public class Backpack01 {
static int bagV = 5;
//花费
static int[] nCost = {0, 3, 5, 7};
//物体体积
static int[] nVol = {0, 2, 3, 4};

static int[][] maxGetMnery = new int[nCost.length][bagV + 1];

private static int dpCalculateMoney(int n, int remainV) {
if (remainV < nVol[n]) {
if (maxGetMnery[n - 1][remainV] == -1) {
maxGetMnery[n - 1][remainV] = dpCalculateMoney(n - 1, remainV);
}
maxGetMnery[n][remainV] = maxGetMnery[n - 1][remainV];
} else {
if (maxGetMnery[n - 1][remainV] == -1) {
maxGetMnery[n - 1][remainV] = dpCalculateMoney(n - 1, remainV);
}
if (maxGetMnery[n - 1][remainV - nVol[n]] == -1) {
maxGetMnery[n - 1][remainV - nVol[n]] = dpCalculateMoney(n - 1, remainV - nVol[n]);
}
maxGetMnery[n][remainV] = Math.max(maxGetMnery[n - 1][remainV - nVol[n]] + nCost[n], maxGetMnery[n - 1][remainV]);
}

return maxGetMnery[n][remainV];
}

public static void main(String[] args) {
for (int i = 0; i < nCost.length; i++) {
for (int j = 0; j < bagV + 1; j++) {
if (i == 0 || j == 0) {
maxGetMnery[i][j] = 0;
} else {
maxGetMnery[i][j] = -1;
}
}
}
dpCalculateMoney(nCost.length - 1, bagV);
System.out.println(maxGetMnery);
}
}
坚持原创技术分享,您的支持将鼓励我继续创作!