焦作网站建设哪家便宜,宁波网络公司选哪家,拿了网赌代理后怎样做自己的网站,在阿里巴巴做网站西安交大 软件53 蔡少斐 题号#xff1a;3_14
题目叙述#xff1a;
某商店中每种商品都有一个价格。例如#xff0c;一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位#xff09;;一个花瓶的价格是5 ICU。为了吸引更多的顾客#xff0c;商店提供了特殊优惠价。 特殊优…
西安交大 软件53 蔡少斐 题号3_14
题目叙述
某商店中每种商品都有一个价格。例如一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位;一个花瓶的价格是5 ICU。为了吸引更多的顾客商店提供了特殊优惠价。 特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。 编一个程序计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意你不能变更顾客所购商品的种类及数量即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14ICU因为: 1朵花加2个花瓶: 优惠价:10 ICU 2朵花 正常价: 4 ICU
输入数据 用两个文件表示输入数据。第一个文件INPUTTXT描述顾客所购物品放在购物筐中;第二个文件描述商店提供的优惠商品及价格文件名为OFFERTXT。 两个文件中都只用整数。 第一个文件INPUTTXT的格式为:第一行是一个数字B0≤B≤5表示所购商品种类数。下面共B行每行中含3个数CKP。C 代表商品的编码每种商品有一个唯一的编码1≤C≤999。K代表该种商品购买总数1≤K≤5。P 是该种商品的正常单价每件商品的价格1≤P≤999。请注意购物筐中最多可放5*525件商品。
第二个文件OFFERTXT的格式为:第一行是一个数字S0≤S≤99表示共有S种优惠。下面共S行每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对CK其中C代表商品编码1≤C≤9 99。K代表该种商品在此组合中的数量1≤K≤5。本行最后一个数字P1≤P≤9999代表此商品组合的优惠价。当然优惠价要低于该组合中商品正常价之总和。
输出数据
在输出文件OUTPUTTXT中写一个数字占一行 该数字表示顾客所购商品输入文件指明所购商品应付的最低货款。
题目解答
本题应该采用动态规划的方法进行设计定义本题的最优子结构以及状态为一个五元组dp[x1][x2][x3][x4][x5]其中x1代表要买的第一种物品的个数x2代表要买的第二种物品的个数、以此类推。由于题目保证了B5因此5元组绝对够用。
我们用一个std::vector来存储每套组合方案的捆绑的种类以及该种类需要购买的数量。
下面我们假定不需要的物品一个都不能买需要的物品也不能够多买。
要列出该5元组的状态转移方程其中优惠集合记为S。 .
在代码实现的时候采用了备忘录技术。
代码表示 #include iostream
#include vector
#include algorithm
using namespace std;
typedef pairint, int P;
const int MAX 6;
const int INF 1e9;
int map[1000];
int n, m;
int ids[MAX];
int price[MAX];
int nums[MAX];
vectorP pairs[100];
int pP[100];
int pcnt 0;
int dp[MAX][MAX][MAX][MAX][MAX];
int times 0;
int dfs( int* x )
{times;int r dp[x[0]][x[1]][x[2]][x[3]][x[4]];if ( r 0 ){return(r);}if ( x[0] 0 x[1] 0 x[2] 0 x[3] 0 x[4] 0 ){return(0);}int minf INF;for ( int i 0; i pcnt; i ){vectorP vec pairs[i];int f 1;int *y new int[5];for ( int t 0; t 5; t )y[t] 0;for ( auto p : vec ){int id map[p.first];int num p.second;if ( x[id] num ){f 0; break;}y[id] -num;}if ( !f )continue;for ( int k 0; k 5; k )y[k] x[k];minf min( minf, pP[i] dfs( y ) );}int s 0;for ( int i 0; i 5; i ){s x[i] * price[i];}minf min( minf, s );return(dp[x[0]][x[1]][x[2]][x[3]][x[4]] minf);
}int main()
{cin n;for ( int i 0; i n; i ){int C, K, PP;cin C K PP;ids[i] C;nums[i] K;price[i] PP;if ( !map[C] ){map[C] i;}}cin m;for ( int i 0; i m; i ){int k; cin k;vectorP v;int f 1;for ( int j 0; j k; j ){int a, b; cin a b;v.push_back( make_pair( a, b ) );}int PP;cin PP;if ( f ){pairs[pcnt] v;pP[pcnt] PP;}}cout 答案: dfs( nums ) endl;cout 运行次数: times endl;return(0);
}运行结果
