买花最少花费问题（java版带详细注释）

买花最少花费问题

问题描述

商店中每种商品都有标价。例如，一朵花的价格是 2 元。一个花瓶的价格是 5 元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销售。例如，3 朵花的价格不是 6 元而是 5 元。2 个花瓶加 1 朵花的优惠价是 10 元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。

对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。

算法分析与设计

最优子结构证明：

设$cost(a,b,c,d,e)$表示购买商品组合$(a,b,c,d,e)$需要的最少费,$A[K],B[K],C[K],D[K],E[k]$表示第k种优惠方案。$offer(m)$是第$m$种优惠方案的价格，如果$cost(a,b,c,d,e)$使用了第$m$种优惠方案，则
$$cost(a,b,c,d,e)=cost(a-A[m],b-B[m],c-C[m],d-D[m],e-E[m])+offer(m)$$
即该问题具有最优子结构性质。

代码说明

package edu.xjtu.work3_14;import java.util.Scanner;public class Main {// 商品编码的最大值private static final int MAXCODE = 999;// 优惠商品组合数private static final int SALECOMB = 99;// 商品种类private static final int KIND = 5; // 购买某种商品数量的最大值private static final int QUANTITY = 5;// 记录商品编码与商品种类的对应关系private static final int[] num = new int[MAXCODE + 1];// 记录不同种类商品的购买数量private static final int[] product = new int[KIND + 1];// offer[i][j]: 商品组合的优惠价(j=0)；某种优惠组合中某种商品需要购买的数量(j>0)private static final int[][] offer = new int[SALECOMB + 1][KIND + 1];// 记录不同商品的购买数量和购买价格private static final Goods[] goods = new Goods[KIND + 1];// 记录本次购买的总花费private static final int[][][][][] cost = new int[QUANTITY + 1][QUANTITY + 1][QUANTITY + 1][QUANTITY + 1][QUANTITY + 1];private static int b;// 购买商品种类数private static int s;// 当前优惠组合数public static void main(String[] args) {// 读入数据readInput();// 动态规划求最优解comp(1);// 输出out();}/*** 动态规划求最优解** @param i 下标*/private static void comp(int i) {if (i > b) {minicost();return;}for (int j = 0; j <= goods[i].getSum(); j++) {product[i] = j;comp(i + 1);}}/*** 初始化数据*/private static void readInput() { // 初始化数据Scanner input = new Scanner(System.in);int i, j, n, p, t, code;for (i = 0; i < 100; i++)for (j = 0; j < 6; j++)offer[i][j] = 0;for (i = 0; i < 6; i++) {goods[i] = new Goods();goods[i].setSum(0);goods[i].setPrice(0);product[i] = 0;}b = input.nextInt(); // 购买商品种类数for (i = 1; i <= b; i++) {code = input.nextInt();goods[i].setSum(input.nextInt());goods[i].setPrice(input.nextInt());num[code] = i;}s = input.nextInt(); // 当前优惠组合数for (i = 1; i <= s; i++) {t = input.nextInt();for (j = 1; j <= t; j++) {n = input.nextInt();p = input.nextInt();offer[i][num[n]] = p;}offer[i][0] = input.nextInt();}}/*** 计算最小花费*/private static void minicost() {int i, j, k, m, n, p, minm;minm = 0;for (i = 1; i <= b; i++)minm += product[i] * goods[i].getPrice();for (p = 1; p <= s; p++) {i = product[1] - offer[p][1];j = product[2] - offer[p][2];k = product[3] - offer[p][3];m = product[4] - offer[p][4];n = product[5] - offer[p][5];if (i >= 0 && j >= 0 && k >= 0 && m >= 0 && n >= 0 && cost[i][j][k][m][n] + offer[p][0] < minm)minm = cost[i][j][k][m][n] + offer[p][0];}cost[product[1]][product[2]][product[3]][product[4]][product[5]] = minm;}/*** 输出*/private static void out() {System.out.println(cost[product[1]][product[2]][product[3]][product[4]][product[5]]);}
}

package edu.xjtu.work3_14;public class Goods {private int price;// 购买价格private int sum;// 购买数量public int getPrice() {return price;}public void setPrice(int price) {this.price = price;}public int getSum() {return sum;}public void setSum(int sum) {this.sum = sum;}
}

运行结果展示