DP + 01背包问题:饭卡

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。DP + 01背包问题:饭卡,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

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

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!