1.问题描述： 商店中每种商品都有标价。例如，一朵花的价格是 2 元，一个花瓶的价格是 5 元。为了 吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销 售。例如，3 朵花的价格不是 6 元而是 5 元，2 个花瓶加 1 朵花的优惠价是 10 元。试设计一 算法，计算出某一顾客所购商品应付的最少费用。
2.算法设计： 对于给定欲购商品的价格和数量，以及优惠商品价，计算所购商品应付的最少费用。 数据输入：
提供欲购商品数据。第 1 行中有 1 个整数 B（0≤B≤5），表示所购商品种类数。接下来的 B 行，每行有 3 个数 C，K 和 P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。 K 表示购买该种商品总数，1≤K≤5。P是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多购买 5x5=25 件商品。提供优惠商品价数据。第 1 行中有 1 个整数 S（0≤S≤99），表示共有 S 种优惠商品组合。接下来的 S 行，每行的第 1 个数描述优惠商品组合中商品的种类数 j。接着是 j 个数字对（C，K），其中 C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后 1 个数字 P（1≤P≤9999）表示此商品组合的优惠价。 数据输出：输出计算出的所购商品应付的最少费用。 例： 输入： 2 2 7 3 2 1 7 3 5 8 2 5 2 7 1 8 2 10 输出： 14 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <set> #include <map> #include <time.h> using namespace std; int sale[1000][6] = { 0 }; //分别表示每个优惠中每个商品数量 int saleprice[1000] = { 0 }; //优惠的价格 int salelength[1000] = { 0 }; //优惠总共有几个商品 int salenumber[1000][1000] = { 0 }; //优惠商品的ID int good[6][4] = { 0 }; //1 -> number 2 -> price 3 -> last num int num[1000]; //商品ID int dp[6][6][6][6][6]; int n, m; void input() { cin >> n; for (int i = 1; i <= n; i++) { cin >> good[i][1] >> good[i][3] >> good[i][2]; num[i] = good[i][1]; } cin >> m; for (int i = 1; i <= m; i++) { cin >> salelength[i]; for (int j = 1; j <= salelength[i]; j++) { cin >> salenumber[i][j]; cin >> sale[i][salenumber[i][j]]; } cin >> saleprice[i]; } } int main() { input(); dp[0][0][0][0][0] = 0; for (int i = 0; i <= good[1][3]; i++) for (int j = 0; j <= good[2][3]; j++) for (int k = 0; k <= good[3][3]; k++) for (int l = 0; l <= good[4][3]; l++) for (int p = 0; p <= good[5][3]; p++) { int minx = i * good[1][2] + j * good[2][2] + k * good[3][2] + l * good[4][2] + p * good[5][2]; for (int q = 1; q <= m; q++) { if (i - sale[q][num[1]] < 0 || i - sale[q][num[2]] < 0 || i - sale[q][num[3]] < 0 || i - sale[q][num[4]] < 0 || i - sale[q][num[5]] < 0) continue; int t = dp[i - sale[q][num[1]]][j - sale[q][num[2]]][k - sale[q][num[3]]][l - sale[q][num[4]]][p - sale[q][num[5]]] + saleprice[q]; if (t < minx) minx = t; } dp[i][j][k][l][p] = minx; } cout << dp[good[1][3]][good[2][3]][good[3][3]][good[4][3]][good[5][3]] << endl; return 0; }