jacky

最少费用购物 Description ?问题描述： 商店中每种商品都有标价。例如，一朵花的价格是2元。一个花瓶的价格是5 元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价售。例如，3朵花的价格不是6元而是5元。2 个花瓶加1 朵花的优惠价是10 元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。 ?编程任务： 对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。 Input 由文件input.txt提供欲购商品数据。文件的第1行中有1 个整数B（0≤B≤5），表示所购商品种类数。接下来的B 行，每行有3 个数C，K 和P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。K 表示购买该种商品总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多可购买5*5＝25件商品。由文件offer.txt提供优惠商品价数据。文 件的第1行中有1 个整数S（0≤S≤99），表示共有S 种优惠商品组合。接下来的S 行，每行的第一个数描述优惠商品组合中商品的种类数j。接着是j 个数字对（C，K），其中C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后一个数字P（1≤ P≤9999）表示此商品组合的优惠价。 Output 程序运行结束时，将计算出的所购商品应付的最少费用输出到文件output.txt中。 Sample Input input.txt 2 7 3 2 8 2 5 offer.txt 2 1 7 3 5 2 7 1 8 2 […]

用2 台处理机A 和B 处理n个作业。设第i 个作业交给机器A 处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性 能关系，很可能对于某些i，有ai>=bi，而对于某些j，j≠i，有aj<bj，既不能将一个作业分开由2 台机器处理，也没有一台机器能 同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。 input 6 2 5 7 10 5 2 3 8 4 11 3 4 output15 //独立任务调度 #include<iostream> #include<vector> using namespace std; const int n=6; int a1[]={2,5,7,10,5,2}; int b1[]={3,8,4,11,3,4}; class tree { public: int a,b; }; int main() { cout<<“******************************************”<<endl; cout<<”         任务调度情况如下:”<<endl; cout<<”       (1)作业数目:”<<n<<endl; cout<<”       (2)各作业处理时间:”<<endl; cout<<”       “; for(int aj=0;aj<n;aj++) cout<<a1[aj]<<” “; cout<<endl; cout<<”       “; for(int bj=0;bj<n;bj++) cout<<b1[bj]<<” […]

【实验目的】 练习掌握动态规划算法。 【实验内容】 设计一个O(n*n)时间的算法，找出由n个数组成的序列的最长单调递增子序列。 【实验条件】 Microsoft Visual C++ 6.0 【需求分析】 题目要求在O(n*n)的时间内找出n个数组成的序列的最长单调递增子序列,需要用到排序算法，查找最长公共子序列的算法。 【设计原理】 将数组a复制到数组x,先用排序算法将数组x排序，在调用查找最长公共子序列的算法求出数组a和数组x中的最长公共子序列，因为数组x是单调递增的，所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。 【概要设计】 数据： N：数组元素个数。 a[N]：用于存放数组。 X[N]：复制数组a[N]，并排序。 c[i][j]：存储a和x的最长公共子序列的长度。 b[i][j]：记录c[i][j]的值是由哪一个资问题的解得到的。 函数： int Partition(int a[],int p,int t,int x); //数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。 void Swap(int &x,int &y); //交换元素x和y。 void QuickSort(int a[],int p,int r); //快速排序。 void LCSL(int m,int n,int *x,int *y,int **c,int **b); //计算最长公共子序列长度。 void LCS(int […]

/* 课本0-1背包。 程序功能：将物体只能一次放入包中，要不超过总量 且 价值最大 经过vc8.0编译通过 * */ #include <iostream> using namespace std; #define N 10 #define C 50 void knapsack(int * v,int *w,int wlength,int c,int(*m)[C+1]) { int n=wlength-1; int jmax=std::min(w[n]-1,c); for(int j=0;j<=jmax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i–) { jmax=std::min(w[i]-1,c); for(int j=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=std::max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=std::max(m[1][c],m[2][c-w[1]]+v[1]); } […]

/* 课本 0-1背包 加上体积限制。 程序功能：将物体只能一次放入包中，要不超过总量、总体积且 价值最大 经过vc8.0编译通过 * */ #include <iostream> #include <iomanip> using namespace std; #define N 10     //物品的可选数量 #define C 40     //包的最大可容纳重量 #define E   28     //包的最大可容纳体积   //动态规划算法 void knapsack(int * v,int *w,int wlength,int c,int *e,int ee,int (*m)[C+1][E+1]) { int n=wlength-1; //—————————————– //递归计算的第一步 //求出当物品只有n的解 int jmax  = std::min(w[n]-1,c); int jmax2 = std::min(e[n]-1,ee); for(int j=0;j<=jmax;j++) for(int k=0;k<=jmax2;k++) m[n][j][k] = 0; […]

/* 课本3-1-1。 程序功能：求解最长公共递增子序列 经过vc8.0编译通过 * */ #include <iostream> #include <string.h> using namespace std; #define N  11 //——————————————————— //最长公共子序列求解 int lcslength(int * x,int m,int * y,int n,int (*b)[N]) { int c[N][N]; int i; for(i=0;i<=n;i++) {c[0][i]=0;c[i][0]=0;} for(i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } […]

最长单调递增子序列问题的定义：      设计一个O(n2)时间的算法，找出由n个数组组成的序列的最长单调递增子序列。 子问题的定义：      对于求解N规模的数组，n-1,n-2,…,1 长度的数组构成了问题的子问题，子问题的详细定义是：求解以第n-1,n-2,…,1 个元素为最大值的最长子序列。 最优子结构：      第n个元素的最长子序列的长度是基于前n-1个元素最长子序列的基础之上，也就是第n个元素的最长子序列长度，是前n个元素的中最长的子序列长度+1。 解决的办法：      从第1个元素开始进行循环，不断地求出1,2,3,..,n元素为最大值的最长子序列长度，然后通过回溯查找最长子序列。 具体算法： Input 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开 Output 最长单调递增子序列，数字之间用空格格开 Sample Input 5 1 3 5 2 9 Sample Output 1 3 5 9 C程序： #include <stdio.h> #include <stdlib.h> void findAllMax(int *,int *,int *,int); void trackBack(int *,int *,int *,int); […]

After finished <Basic Engish> course & <engineering mathimatics> course, we started <Design and analysis of algorithms>. Frankly, I don’t familiar with most of them, although I’m a programmer with over ten years of experiences. I believe the reason of this is I’m not an algorithm researcher, but IMHO most of […]

这是视频的演讲者是 Simon Sinek。这也是一个非常不错的演讲，当然这并不一定代表认同他对一些公司的看法和讲法，但重要的那种思想。我们做事件和表达必须从内而外。而不是自外而内。作为一点衔接，让我感触较深的是，就是前面提到我听：Richard St. John: 8 secrets of success这篇文章一样，作为一名员工，必须用心去做事，才可能成为一名好员工。举个例子： 公司从来不主动要求员工加班，但必如果一个员工真的认为自己的成长是跟公司、跟工作紧密连接在一起的，那不用要求，他自己就要用心，甚至拼了老命去工作。就像他提到的那样：The goal is not just to hire people who need a job; it’s to hire people who believe what you believe. I always say that, you know, if you hire people just because they can do a job, they’ll work for […]

精华课程分享：成功的8个秘诀。 这是一篇很短的TED视频，只有3分多钟，但完全可以说“浓缩的都是精华”。 其中最让我深有感触的，也是我选择把这篇演讲放上来的原因是这一句话：Carol Coletta says, “I would pay someone to do what I do.” 我所在的公司其实一直都没怎么赚到钱，但是我们的老板却一直一直一直在往里边投钱，而且在许多时候的许多决策都让我们许多人都看不懂（废话，你要是看懂了，你不也成了Chairman of the Board了？）。 举个例子来说：我们今年不卖XXXX产品，RD努力做好XXXX产品。 OK，我明白，单纯这样讲可能你看不懂，那我换个说法：RD不要理会Sales的那些XXXX产品有YYYY bug、缺ZZZZ功能的抱怨（事实上连RD都知道有些问题很急，甚至有可能RD稍微努力的去配合一下，KKKK项目就能成功了），我想要做的是另外一个 功能/产品，而这个新功能/新产品可能几年内都带不来一分钱的收入，但谈下这个KKKK项目有可能会带来可观的收入，对业务的拓展及数年来的亏损有所帮 助…… 这样讲，也许你能有一点点的明白了吧？ 所以，当我在课堂上听到这句话的时候 Carol Coletta says, “I would pay someone to do what I do.”，真的被深深的感触到了，我们的董事长经营这家公司就是为了一种热爱，他爱这个产品，所以他愿意为这个产品投入大笔大笔的钱（哪怕连续的亏损），同时，他也愿意付钱给同样热爱这个产品的人让他们跟他一起工作。 以下为我专门到网上搜到的这个视频相关的英文原文： Richard St. John: 8 secrets of success http://www.ted.com/talks/richard_st_john_s_8_secrets_of_success.html About this talk Why […]