请教一个先进先出算法的实现

xyzlsh

有个问题，想用shell或者perl解决，折腾几天也没弄出来，麻烦指点一下，问题如下：
从下表第2列的原始铅笔数量中里取一定数量的铅笔（x），先取批次靠前的，计算每次取出铅笔的总价值f(x),取得铅笔是哪个批次，就选择相应批次的单价。
铅笔批次 原始铅笔数量 单价 本次取出数量 剩余铅笔数量
1 150 0.6 0 150
2 150 0.7 0 150
3 100 0.5 0 150
4 10 0.6 0 10
5 100 0.7 0 100
6 120 0.55 0 120

例子如下：
如果在第1次取100支铅笔，上表中铅笔数量变化如下：
铅笔批次 原始铅笔数量 单价 本次取出数量 剩余铅笔数量
1 150 0.6 100 50
2 150 0.7 0 150
3 100 0.5 0 150
4 10 0.6 0 10
5 100 0.7 0 100
6 120 0.55 0 120
相应的f(100)=100*0.6=60
如果在第2次取120支铅笔，即f(120)，上表中铅笔数量变化如下：
铅笔批次 原始铅笔数量 单价 剩余铅笔数量
1 150 0.6 50 0
2 150 0.7 70 80
3 100 0.5 0 150
4 10 0.6 0 10
5 100 0.7 0 100
6 120 0.55 0 120
f(120)=50*0.6+50*0.7=65
如果在第3次取250支铅笔，即f(250)，上表中铅笔数量变化如下：
铅笔批次 原始铅笔数量 单价 剩余铅笔数量
1 150 0.6 0 0
2 150 0.7 80 0
3 100 0.5 150 0
4 10 0.6 10 0
5 100 0.7 10 90
6 120 0.55 0 120
f(250)=80*0.7+150*0.5+10*0.6+10*0.7

[ 本帖最后由 xyzlsh 于 2009-5-20 16:11 编辑 ]

kwokcn

单句awk处理。每次处理输出本次的购货款，更新原文件状态。

1. 
   
2. awk -v n=100 'NR==1{print > FILENAME".bak";next}n>$4{n=n-$4;$NF=$4;$4="0"}n<=$4{$NF=n;$4=$4-n;n="0"}{print > FILENAME".bak";s=s+$3*($NF)}END{printf("%0.2f\n",s); system("mv "FILENAME".bak "FILENAME)}' URFILE
   

复制代码

可以处理任意情况（为显示清楚每次处理手动加空行）：

1. 
   
2. [root]# cat aa
   
3. 铅笔批次 原始铅笔数量 单价 剩余铅笔数量 本次取出数量
   
4. 1 150 0.6 150 0
   
5. 2 150 0.7 150 0
   
6. 3 100 0.5 100 0
   
7. 4 10 0.6 10 0
   
8. 5 100 0.7 100 0
   
9. 6 120 0.55 120 0
   
10. 
    
11. [root]# awk -v n=280 'NR==1{print > FILENAME".bak";next}n>$4{n=n-$4;$NF=$4;$4="0"}n<=$4{$NF=n;$4=$4-n;n="0"}{print > FILENAME".bak";s=s+$3*($NF)}END{printf("%0.2f\n",s); system("mv "FILENAME".bak "FILENAME)}' aa
    
12. 181.00
    
13. 
    
14. [root]# cat aa
    
15. 铅笔批次 原始铅笔数量 单价 剩余铅笔数量 本次取出数量
    
16. 1 150 0.6 0 150
    
17. 2 150 0.7 20 130
    
18. 3 100 0.5 100 0
    
19. 4 10 0.6 10 0
    
20. 5 100 0.7 100 0
    
21. 6 120 0.55 120 0
    
22. 
    
23. [root]# awk -v n=280 'NR==1{print > FILENAME".bak";next}n>$4{n=n-$4;$NF=$4;$4="0"}n<=$4{$NF=n;$4=$4-n;n="0"}{print > FILENAME".bak";s=s+$3*($NF)}END{printf("%0.2f\n",s); system("mv "FILENAME".bak "FILENAME)}' aa
    
24. 167.50
    
25. 
    
26. [root]# cat aa
    
27. 铅笔批次 原始铅笔数量 单价 剩余铅笔数量 本次取出数量
    
28. 1 150 0.6 0 0
    
29. 2 150 0.7 0 20
    
30. 3 100 0.5 0 100
    
31. 4 10 0.6 0 10
    
32. 5 100 0.7 0 100
    
33. 6 120 0.55 70 50
    
34. 
    
35. [root]# awk -v n=280 'NR==1{print > FILENAME".bak";next}n>$4{n=n-$4;$NF=$4;$4="0"}n<=$4{$NF=n;$4=$4-n;n="0"}{print > FILENAME".bak";s=s+$3*($NF)}END{printf("%0.2f\n",s); system("mv "FILENAME".bak "FILENAME)}' aa
    
36. 38.50
    
37. 
    
38. [root]# cat aa
    
39. 铅笔批次 原始铅笔数量 单价 剩余铅笔数量 本次取出数量
    
40. 1 150 0.6 0 0
    
41. 2 150 0.7 0 0
    
42. 3 100 0.5 0 0
    
43. 4 10 0.6 0 0
    
44. 5 100 0.7 0 0
    
45. 6 120 0.55 0 70
    
46. 
    
47. [root]# awk -v n=280 'NR==1{print > FILENAME".bak";next}n>$4{n=n-$4;$NF=$4;$4="0"}n<=$4{$NF=n;$4=$4-n;n="0"}{print > FILENAME".bak";s=s+$3*($NF)}END{printf("%0.2f\n",s); system("mv "FILENAME".bak "FILENAME)}' aa
    
48. 0.00
    
49. 
    
50. [root]# cat aa
    
51. 铅笔批次 原始铅笔数量 单价 剩余铅笔数量 本次取出数量
    
52. 1 150 0.6 0 0
    
53. 2 150 0.7 0 0
    
54. 3 100 0.5 0 0
    
55. 4 10 0.6 0 0
    
56. 5 100 0.7 0 0
    
57. 6 120 0.55 0 0

复制代码

[ 本帖最后由 kwokcn 于 2009-5-20 18:52 编辑 ]

wtuter

变量a为你要抽取的数量


a=50;awk '{print $1,$2,$3,$3*'"$a"',$2-'"$a"'}' 2
1 150 0.6 30 100
2 150 0.7 35 100
3 100 0.5 25 50
4 10 0.6 30 -40
5 100 0.7 35 50
6 120 0.55 27.5 70

[ 本帖最后由 wtuter 于 2009-5-20 15:57 编辑 ]

kwokcn

最后要求输出什么呢？
表的最终状态还有f(n)的值吗？

xyzlsh

至少要输出如下的信息：
1.每批铅笔的单价；
2.每次出货后，铅笔的剩余数量。

wtuter

a=50;awk '{print $1,$2,$3,$3*'"$a"',$2-'"$a"'}' 2


$1 $2 $3 $4  $5   
           单价   剩余数量
1 150 0.6 30 100
2 150 0.7 35 100
3 100 0.5 25 50
4 10 0.6 30 -40
5 100 0.7 35 50
6 120 0.55 27.5 70

xyzlsh

问题好像没这么简单，不能用$2直接减去a。因为是按照批次取货，如果上批还有剩余，会把上批取到0，再取本批。还要注意每次出货后都要更新存货的状态，所以理论上每次函数计算的结果可能会有不同。

[ 本帖最后由 xyzlsh 于 2009-5-20 16:22 编辑 ]

kwokcn

改进后写在8楼了。

[ 本帖最后由 kwokcn 于 2009-5-20 18:54 编辑 ]

ubuntuer

1. awk -v total=$total '{a[NR]=$1" "$2" "$3;b[NR]=$4;c[NR]=$5}END{for(i=1;i<=NR;i++){sum+=c[i];if(total){if(sum>total){b[i]=c[i];c[i]=sum-total;b[i]-=c[i];total=0;}else{b[i]=c[i];c[i]=0}}print a[i]" "b[i]" "c[i]}}' file
   

复制代码

上次处理的没写入文件

1. total=600
   
2. [root@mip-123456 shell]# awk -v total=$total '{a[NR]=$1" "$2" "$3;b[NR]=$4;c[NR]=$5}END{for(i=1;i<=NR;i++){sum+=c[i];if(total){if(sum>total){b[i]=c[i];c[i]=sum-total;b[i]-=c[i];total=0;}else{b[i]=c[i];c[i]=0}}print a[i]" "b[i]" "c[i]}}' file
   
3. 1 150 0.6 150 0
   
4. 2 150 0.7 150 0
   
5. 3 100 0.5 150 0
   
6. 4 10 0.6 10 0
   
7. 5 100 0.7 100 0
   
8. 6 120 0.55 40 80

复制代码

woodie

shell和awk混合的，每次备份原来的文件，未考虑库存不足时的情况：

1. #!/bin/sh
   
2. [ $# -lt 2 ] &&  { echo "Usage: $0 amount file" ;exit 1; }
   
3. 
   
4. awk -v zl=$1 'BEGIN{over=start=0;}
   
5. $5!=0&&!over{
   
6.   dj[NR]=$3;
   
7.   if (start==0) start=NR;
   
8.   sl[NR]=($5>=zl)?zl:$5;
   
9.   $4=sl[NR];
   
10.   $5=$5-sl[NR];
    
11.   zl-=sl[NR];
    
12.   if(zl==0){
    
13.     for(i=start;i<=NR;i++) {
    
14.       je+=sl[i]*dj[i];
    
15.     }
    
16.     print je;
    
17.     over=1;
    
18.   };
    
19. }
    
20. {print > "file-new";}' $2
    
21. 
    
22. mv $2 ${2}-"$(date)"
    
23. mv file-new $2

复制代码