我想做个网站 详解怎么做,制作网站软件免费,网页设计作业笔记,wordpress CDN设置贪心#xff0c;顾名思义#xff0c;就是挑价值最大的
如果直接挑价值最大的#xff0c;这样不一定能够达到最优解#xff0c;因为最终价值多少还要取决于背包容量。
贪心算法解决0-1背包问题的基本思路是#xff1a;按照物品的单位价值#xff08;即价值与重量的比值顾名思义就是挑价值最大的
如果直接挑价值最大的这样不一定能够达到最优解因为最终价值多少还要取决于背包容量。
贪心算法解决0-1背包问题的基本思路是按照物品的单位价值即价值与重量的比值从高到低进行排序然后依次选择单位价值最高的物品放入背包直到背包装满或者所有物品都已经被考虑过。
具体步骤如下 首先我们需要将所有的物品按照单位价值进行排序。单位价值最高的物品排在最前面。 然后我们从单位价值最高的物品开始依次考虑是否将其放入背包。如果当前物品的重量加上已经放入背包的物品的总重量不超过背包的容量那么我们就将其放入背包。 如果当前物品的重量加上已经放入背包的物品的总重量超过了背包的容量那么我们就放弃放入这个物品。 重复上述步骤直到背包装满或者所有物品都已经被考虑过。
这种方法的优点是简单易懂计算速度快。但是它只能得到问题的局部最优解不能保证得到全局最优解。 这也是贪心的典型题目之一先看题目要求LeetCode860在柠檬水摊上每一杯柠檬水的售价为5美元。顾客排队购买你的产品按账单bills支付的顺序一次购买一杯。每位顾客只买一杯柠檬水然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付5美元。
输入bi11s[5,5,5,10,20] 输出true
public boolean lemonadeChange(int[] bills) {// 这里只表示5元和10元纸币的数量而不是总金额int cash_5 0;int cash_10 0;for (int i 0; i bills.length; i) {if (bills[i] 5) {cash_5;} else if (bills[i] 10) {cash_5--;cash_10;} else if (bills[i] 20) {if (cash_10 0) {cash_10--;cash_5--;} else {cash_5 - 3;}}if (cash_5 0 || cash_10 0) return false;}return true;
} 1.如果给的是5那么直接收下。 2.如果给的是10元那么收下一个10给出一个5此时必须要有一个5才行。 3.如果给的是20那么优先消耗一个10元再给一个5元。假如没有10元则给出3个5元。
