网站没有做的关键词有排名,icp备案查询官方网站,电商图片制作软件,关于一学一做的短视频网站好淘宝的“双十一”购物节有各种促销活动#xff0c;比如“满 200 元减 50 元”。假设你的购物车中有 n 个#xff08;n100#xff09;想买的商品#xff0c;希望从里面选几个#xff0c;在凑够满减条件的前提下#xff0c;让选出来的商品价格总和最大程度地接近满减条…淘宝的“双十一”购物节有各种促销活动比如“满 200 元减 50 元”。假设你的购物车中有 n 个n100想买的商品希望从里面选几个在凑够满减条件的前提下让选出来的商品价格总和最大程度地接近满减条件200 元这样就可以极大限度地“薅羊毛”。
回溯法
我们假设购物满w元才能减。例如满500减200那w500。购物车中商品的价格int[] price表示。每次决定第i个物品要不要购买当物品选完了或者总价够w停止选择。比较选中物品价格总和最低的一组选择。这是一个多阶段决策最优化问题。可以先用回溯算法解决。
public class Shopping {private int[] price new int[]{198,201,345,200};private int w 500;private int minPrice Integer.MAX_VALUE;private ListInteger selectItems;private void f (int i,int priceSum,boolean[] shoppingStatus){if(priceSumw){if(priceSumminPrice){minPrice priceSum;selectItems new ArrayListInteger();for(int j0;jshoppingStatus.length;j){if(shoppingStatus[j]){selectItems.add(j);}}}return;}if(iprice.length) return;shoppingStatus[i] true;f(i1,priceSumprice[i],shoppingStatus);//选择第i件商品shoppingStatus[i] false;f(i1,priceSum,shoppingStatus);//不选择第i件商品}public void decision(){boolean[] shoppingStatus new boolean[price.length];f(0,0,shoppingStatus);}
}递归树 递归树中的每个节点是一个状态用(i,preSum)表示。i表示将要处理第i个商品。preSum表示当前状态下已经购买商品的价格和。可以看到这里的状态表示的参数基本和f函数的参数是相同的。 在这个例子中(i,preSum)相同的节点正好都只有一个但不排除有多个节点的可能性。
状态表
根据(i,preSum)我们知道用一个二维表可以表示各种不同的状态。第一维行是商品下标第二维列是商品总价。又因为题目要求价格和需要大于w但我们又不能让商品和太大太大优惠就没有必要了。我们需要给商品总价一个最大值3w。
状态表boolean[][] states。 第0个商品决策之后states[0][0]truestates[0][198]true。 第1个商品决策之后states[1][0]truestates[1][201]truestates[1][198]truestates[1][399]true …
我们在states[n-1]从下标w开始找值为true的元素下标。最先找到的就是符合要求的最小价格。 它与莱文斯坦距离、矩阵中的最短路径长度不同的地方是不需要在每一步决策之后只保留最小值其他节点放弃。 我想这里没有放弃其他节点是因为这里的每一个状态可能就是最终答案。第i个商品是不是购买和第i-1个商品决策之后的所有状态有关系。 public void decisionDp(){int n price.length;int maxw 3*w;boolean[][] states new boolean[n][maxw1];states[0][0] true;if(price[0]maxw){states[0][price[0]] true;}for(int i1;in;i){//不购买第i个for(int j0;jmaxw1;j){if(states[i-1][j]){states[i][j] true;}}//购买第i个for(int j 0;jmaxw1;j){if(states[i-1][j]true jprice[i]maxw){states[i][jprice[i]] true;}}}int minPrice -1;for(int j w;jmaxw1;j){if(states[n-1][j]){minPrice j;break;}}//说明有选择if(minPrice!-1){System.out.println(minPrice);int j minPrice;for(int in-1;i1;i--){if(j-price[i]0 states[i-1][j-price[i]]){System.out.println(price[i]);//购买这件商品}}if(j!0){System.out.println(price[0]);}}}当然这道题目还要一个难点是要输出选择了哪些商品。当我们知道满足要求的最低总价是minPrice。也就是说states[n-1][minPrice]true。如果states[n-2][minPrice]true则说明第n-1号物品是被放弃的不购买的。如果states[n-2][minPrice-price[n-1]]true说明是购买第n-1号商品的。继续递归往回查找。
