0/1背包
首先来讲下什么事0/1背包问题,一般都是这样的:有一堆物品,每个物品有重量和价值两个属性,同时有一个背包可以装一定重量的物品,在背包不超重的情况下往背包里装物品,最多能装价值多少的物品.
之所以叫0/1背包是因为每种物品只有一个,只能选择放或者不放.
1.二维数组形式的解法
思想大致是这样的:我们记录之前放入物品的最优状态来求得当前的最优解.
也就是状态转移方程
dp[i][j] = Math.max(dp[i - 1][j - obj[i][w]] + obj[i][v], dp[i - 1][j])
import java.util.Arrays;
import java.util.Scanner;
public class Task01 {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] obj = new int[n + 1][2];
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i < obj.length; i++) {
obj[i][0] = scanner.nextInt();
obj[i][1] = scanner.nextInt();
}
for (int i = 1; i < obj.length; i++) {
for (int j = 1; j < dp[i].length; j++) {
if (j - obj[i][0] >= 0)
dp[i][j] = Math.max(dp[i - 1][j - obj[i][0]] + obj[i][1], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
}
for (int i = 0; i <dp.length ; i++) {
System.out.println(Arrays.toString(dp[i]));
}
}
}
样例:
第一行：物品个数N和背包大小M
第二行至第N+1行：第i个物品的重量和价值
4 6
1 4
2 6
3 12
2 7来看下输出的数组(一般情况下第0行和第0列不存数据)
| 第0列 | 第1列 | 第2列 | 第3列 | 第4列 | 第5列 | 第6列 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 4 | 4 | 4 | 4 | 4 | 4 |
| 0 | 4 | 6 | 10 | 10 | 10 | 10 |
| 0 | 4 | 6 | 12 | 16 | 18 | 22 |
| 0 | 4 | 7 | 12 | 16 | 19 | 23 |
第M列表示背包的大小M
第几行表示加入当前物品后的选择
所以dp[4][6]是当前情况的最优解.
2.一维数组形式的解法
一维数组的解法其实是上面二维数组的解法优化而来.如果按照二维的解法,有很多题会声明出很大数组直接MLE内存超限.我们仔细观察上面的解法,就会发发现,除了最后一行以外其他的数据都是多余的.
所以我们只保留一行数组就可以了,但是数组的更新顺序需要调整一下.从1->M的话更新的数据会受到当前行更新数据的影响,但是从M->1就完全受影响.
稍作修改把代码变成这样就可以了.
import java.util.Arrays;
import java.util.Scanner;
public class Task01 {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] obj = new int[n + 1][2];
int[] dp = new int[m + 1];
for (int i = 1; i < obj.length; i++) {
obj[i][0] = scanner.nextInt();
obj[i][1] = scanner.nextInt();
}
for (int i = 1; i < obj.length; i++) {
for (int j = dp.length - 1; j > 0; j--) {
if (j - obj[i][0] >= 0)
dp[j] = Math.max(dp[j - obj[i][0]] + obj[i][1], dp[j]);
}
}
System.out.println(Arrays.toString(dp));
}
}完全背包
完全背包问题的表述和0/1背包大致上一样,但是完全背包的物品数量没有限制.
也就是说一个物品可以放入很多次.
完全背包的解法也和0/1背包非常相似,只要把上面0/1背包的M->1的更新方式变成1->M的更新方式就可以了.
仔细想一下我们为什么要把原先的二维数组解法换成一维的时候把更新方式倒过来?如果不倒过来会出现什么情况?
import java.util.Arrays;
import java.util.Scanner;
public class Task01 {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] obj = new int[n + 1][2];
int[] dp = new int[m + 1];
for (int i = 1; i < obj.length; i++) {
obj[i][0] = scanner.nextInt();
obj[i][1] = scanner.nextInt();
}
for (int i = 1; i < obj.length; i++) {
for (int j = 1; j < dp.length; j++) {
if (j - obj[i][0] >= 0)
dp[j] = Math.max(dp[j - obj[i][0]] + obj[i][1], dp[j]);
}
}
System.out.println(Arrays.toString(dp));
}
}
多重背包
多重背包是在01背包的基础上，加了个条件：第 i 件物品有ni件。
解法一般是把多重背包d转化为01背包,那么如何转化呢?
一般是把物品数量转化成 1 2 4 ...这样的二进制打包起来,其实这样是为了能够组合出各种数量的原物品.
比如:某件物品有5个,我们把它转化为1 2 2,如果这件物品放1或者2个时候最优,那么直接放就是了;如果是3个话放一个1个的打包和一个2个打包;如果是4个的话放两个2个打包,如果是5的话放一个1个的打包和两个2个的打包.
代码就不写了.
关于动态规划
已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”）
此时，如果把问题规模降到0，即已知A0，可以得到A0->B.
如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法；
对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。
然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：
{A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,…,Ai}->Ai+1. 这种方式就是第二数学归纳法；
对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。
动态规划的使用
最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）