学步园

关于贪心算法的概念、原理这里不想多提，可见百度http://baike.baidu.com/view/298415.htm 。因为是刚刚接触，所以并没什么特别的理解，但因为对C,C++等语言并不了解，这里姑且试着用SAS做两道题。

题1：

100元，50元，20元，10元，5元，2元，1元。你可以假设每种钱币的数量是无限的。现在有一笔交易，需要找个客户m元，请你设计一个算法，使得找给顾客的钱币张数最少。

/*找钱问题*/
data _null_;
       p=100000;
       m=16;
       if 0<m<=p then do;
        a=floor(m/100);
        b=floor((m-100*a)/50);
        c=floor((m-100*a-50*b)/20);
        d=floor((m-100*a-50*b-20*c)/10);
        e=floor((m-100*a-50*b-20*c-10*d)/5);
        f=floor((m-100*a-50*b-20*c-10*d-5*e)/2);
        g=(m-100*a-50*b-20*c-10*d-5*e-2*f);
        num=sum(of a b c d e f g);
        output;
      end;
      put m a b c d e f g num;/*a,...,g是每种钱币对应数量，num是钱币总数*/
 run;

题2：

0_1 背包问题--给定n 件物品和一个背包，物品的重量为weight,其价值为value,背包的容量为W,求从这n 件物品中选取一部分
物品且对每件物品，要么选，要么不选，要求满足被放入背包的物品重量不超过背包的容量。该例数据来源《基于贪心算法的0-1 背包问题》一文。

/*背包问题*/
data beibao;
   input id weight value;/*物品重量，价值*/
   m_value=value/weight;/*平均价值*/
   flag=1;/*标示变量*/
   w=90;/*背包容量*/
cards;
1 10 50
2 30 45
3 40 60
4 20 20
5 10 30
6 20 40
;
run;
proc sort data=beibao out=beibao1;/*按照单位价值排序*/
   by  descending m_value;
run;
data new;
   set beibao1(rename=(weight=temp ));
   by flag;
   if first.flag then do;
      weight=0;
   end;
   weight+temp;
  
   if weight>w then delete;
run;

对上述背包问题稍作修改，如果允许物品分割装入背包，那么背包能够装的物品的最大价值是多少？
这样背包最多装入w重量的物品，对上代码稍作修改：total_value即为所求

data new(keep=id w m_value weight value);
   set beibao1(rename=(weight=temp1 value=temp2 ));
   by flag;
   if first.flag then do;
      weight=0;value=0;
   end;
	  weight+temp1;value+temp2;
run;
data need;
   merge new new(firstobs=2 keep=weight m_value rename=(weight=nextweight m_value=next_mvalue)) ;
   if weight<w & nextweight>w then do;
      total_value=value+(w-weight)*next_mvalue;
   end;
run;