一、背包问题
二、背包与魔法
问题描述
解题思路
解题代码
三、李白打酒加强版数
问题描述
解题步骤
解题代码
一、背包问题
今天就来说一下背包问题吧，就讨论最常说的 0-1 背包问题。描述：
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 w[i]，价值为 v[i]，现在让你用这个背包装物品，最多能装的价值是多少？
举个简单的例子，输入如下：
代码语言：javascript复制N = 4, W = 5
wt = [2, 2, 4,2]
val = [4, 1, 3,2]算法返回 6，选择前两件物品装进背包，总重量 4小于 W，可以获得最大价值 6。
题目就是这么简单，一个典型的动态规划问题。这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。这就是 0-1 背包这个名词的来历。
第一步要明确两点，「状态」和「选择」。
先说状态，只要给几个物品和一个背包的容量限制，就形成了一个背包问题呀。所以状态有两个，就是「背包的容量」和「可选择的物品」。再说选择，对于每件物品，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
首先看看刚才找到[状态]和[选择]，有两个，也就是说我们需要一个二维 dp 数组。
dp[i][w] 的定义如下：对于前 i 个物品，背包的容量为 w情况下可以装的最大价值是 dp[i][w].
第三步，根据「选择」，思考状态转移的逻辑。
简单说就是「把物品 i 装进背包」和「不把物品 i 装进背包」用代码体现出来呢？
这就要结合对 dp 数组的定义，看看这两种选择会对状态产生什么影响：
先重申一下刚才我们的 dp 数组的定义：
dp[i][w] 表示：对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]。
如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。
如果你把这第 i 个物品装入了背包，那么 dp[i][w] 应该等于 v[i-1] dp[i-1][w - w[i-1]]。
综上就是两种选择，我们都已经分析完毕，也就是写出来了状态转移方程
我用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了 w - w[i-1] 可能小于 0 导致数组索引越界的问题
int bag(int W, int N, int[] wt, int[] v) {
assert N == wt.length;
// 定义dp二维数组
int[][] dp = new int[N 1][W 1];
for (int i = 1; i <= N; i ) {
for (int w = 1; w <= W; w ) {
if (w - wt[i - 1] < 0) {
// 这种情况下只能选择不装入背包 角标越界问题
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包，择优
dp[i][w] = Math.max(
dp[i - 1][w - wt[i-1]] v[i-1],
dp[i - 1][w]
);
}
}
}
return dp[N][W];
}至此，背包问题就解决了，相比而言，我觉得这是比较简单的动态规划问题，因为状态转移的推导比较自然，基本上你明确了
dp数组的定义，就可以理所当然地确定状态转移了。
二、背包与魔法
问题描述
小蓝面前有 N 件物品, 其中第 i 件重量是 Wi, 价值是 Vi 。她还有一个背包, 最大承重是 M 。
小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?
特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 K, 同时价值秝倍。(当然小蓝也可以不使用魔法)
输入格式
第一行包含 3 个整数 N、M 和 K 。
以下 N 行, 每行两个整数 Wi 和 Vi 。
输出格式
一个整数代表答案。
鲜梨输入">样例输入">鲜梨输入
代码语言：javascript复制3 10 3
5 10
4 9
3 8样例输出
代码语言：javascript复制26样例说明
选择第二件和第三件物品, 同时对第二件物品使用魔法。
评测用例规模与约定
对于 30% 的数据, 1≤N,M,K≤100.
对于 100% 的数据, 1≤N≤2000,1≤M,K≤10000,0≤Wi,Vi≤10000.
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
