DP + 01背包问题:饭卡
文章目录
01背包问题
01背包问题是指:给定 n 件物品和一个空间为 C 的背包,第i件物品的体积是vi,其价值为wi 。应该如何选择装入背包的物品,在不超过背包容量的前提下,使装入背包中的物品总价值最大?注意每个物品都只有一个,即每个物品都只有装与不装两种情况。
对于01背包问题,首先我们肯定可以使用DFS的方法解决,枚举每个物品装还是不装,使用一个变量ans来保存每种不超过背包体积的方法中,价值最大的那个,那么时间复杂度为O(2^n)。但是这种暴力枚举的方法在n较大的情况下将会超时,我们可以用DP来求解01背包问题。
我们可以依次遍历物品,对于每种物品,都只有两种处理方式,选择装入或不装入。首先我们考虑n=1的情况,就是只有一件物品,如果我们把它装入,那么剩余空间就会减少,但价值会增加。如果不装入,那么剩余空间不会变,但是总价值也不会变化。我们可以把初始情况看作处理了第0件物品之后的情况(第0件物品实际不存在),显然处理第0件物品之后,背包所剩空间为C,价值为0。放了第一件物品之后呢?所剩空间:C-v1,价值:0+w1。不放第一件呢?所剩空间:C,价值:0。也就是说,我们处理完第i件物品后(装或不装),都会有一个对应的背包中物品所占的体积,以及所获得的价值,每次处理一个物品都可能导致状态的转移。
我们可以转换一下思路,把背包容量为0 ~ C的情况都求出来,背包容量大的状态由背包容量小的状态装入了物品而转移得到。那么我们定义一个状态:dp[i][j],即:背包容量为j时,处理完第i件物品后,获得的最大价值。i的范围为1 ~ n,背包容量j的范围为0 ~ C。那么显然有dp[0][0~C]=0;处理第一件物品时,我们可以选择装入也可以选择不装入,若不装入,dp[1][j] = dp[0][j]
,若装入,则dp[1][j]
将从状态dp[0][j - v1]
转移得到,即背包容量大的状态由背包容量小的状态装入了物品而转移得到。我们从其中选择价值最大的情况,即:
dp[1][j]=max(dp[0][j],dp[0][j-v1]+w1)
;
那么推广下去就可以写成:
for (int i = 1; i <= n; i++) {
for (int j = C; j >= 0; j--) {
if (j >= vi) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vi] + wi);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
这里提一句,采用二维dp数组的方式,j从后向前遍历和从前向后遍历都可以
我们最后要求的就是dp[n][C]
,表示背包容量为C时,处理完所有物品得到的最大价值。观察转移方程发现:状态转移时永远是从前一层物品体积较小(容量较小)或相等的状态更新过来,其实dp数组的第一维我们是不需要的。可以这样理解:我们将上述dp二维数组看作一个矩阵,那么某一行的一个状态是由其上一行的两个状态决定的:
我们将dp[i][j]和dp[i – 1][j]重合,也就是说将dp[i][j]视为由自己的上一个状态dp[i – 1][j]与同一行的状态dp[i – 1][j – vi]得到,然后再将dp[i][j]赋给dp[i – 1][j]:
每个状态都可以由其自身(相当于老状态)以及位于它之前的某个状态更新为新状态,也就是说我们可以将原二维dp数组优化为一维dp数组,即:
for (int i = 1; i <= n; i++) {
for (int j = C; j >= 0; j--) {
if (j >= vi) {
dp[j] = Math.max(dp[j], dp[j - vi] + wi);
} else {
dp[j] = dp[j];
}
}
}
我们发现在j < vi
时,dp[j]
将得不到更新,维持原值,相当于无用代码,因此我们删除无用代码,得到01背包问题的终极形态:
for (int i = 1; i <= n; i++) {
for (int j = C; j >= vi; j--) {
dp[j] = Math.max(dp[j], dp[j - vi] + wi);
}
}
上述代码表示:背包容量大的状态由背包容量小的状态装入了物品而转移得到,而每次选择装或不装某个物品都可能导致状态的转移,我们需保存其中背包价值最大的状态
代码中的递推式,其中所蕴含的重要思想是:对于某个背包容量j,其能承载的最大价值,一定是由比它容量少vi的背包装入了体积为vi的物品转移得到。如果领悟了这个01背包问题dp状态转移的关键,或许能直接写出上述终极形态的代码,而不要经过之前的推演了
优化为一维数组形式后,j就必须从后向前开始遍历了,这样才能保证只装一个物品,否则会装多个物品。我们来从前向后遍历试试看看会发生什么,设当前vi = 1,初始dp[0] = 0,然后我们得到dp[1] = 1,相当于装入物品,接着得到dp[2] = dp[1] + 1 = 2,这相当于我们在dp[1]的基础上装入了物品,结果是我们装入了两次物品,不符合01背包的要求。
问题
思路
题目要求我们最后剩余的钱要尽可能少,且给出了一个设定“卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)”,那么我们可以从总金额留出5块钱,这样做有两个好处:
(1)保证了剩余的钱具有买菜功能。(因为我保留了5块钱本金,所以余额一定>=5元,不会遇到即使金额足够也买不了的情况)
(2)可以用这5块钱去买最贵的菜。(利用贪心思想)
接下来的问题就是尽可能把剩下钱花完,也就是用剩余的钱买总价格尽可能贵的菜(最好是全花完),假设分出5块后还剩下x元,那么问题就转换成“给你一个容量为x的背包,有n-1个物品(最贵的菜留着用5块钱去买),每个物品的容量和价值都为v,要你求背包能装的最大价值和”,原问题就被转换成了01背包问题。
我们使用之前的01背包模板,得到dp[m – 5],表示用剩下的钱买菜的最高总价格,然后我们再去买最贵的菜,设其价格为maxPrice,那么答案即为m - dp[m - 5] - maxPrice
代码
import java.util.*;
public class Main {
static int[] price = new int[1005];
static int[] dp = new int[1005];
public static void main(String[] args) {
int n, p, i, m, j, maxIndex, maxPrice;
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
n = scanner.nextInt();
maxIndex = 0;
maxPrice = 0;
for (i = 0;i < n;i++) {
p = scanner.nextInt();
price[i] = p;
if (p > maxPrice) {
maxIndex = i;
maxPrice = p;
}
}
m = scanner.nextInt();
if (m < 5) {
System.out.println(m);
continue;
}
dp[m - 5] = 0;
for (i = 0;i < n;i++) {
if (i == maxIndex) {
continue;
}
for (j = m - 5;j >= price[i];j--) {
dp[j] = Math.max(dp[j], dp[j - price[i]] + price[i]);
}
}
System.out.println(m - dp[m - 5] - maxPrice);
}
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/153727.html