算法复习周------“贪心问题之‘最优装载与背包问题’”

因为这两个算法均属于贪心算法里面的简单算法，所以我把他们写到了一起，这两道题目因为很好理解所以机考的可能也很大，所以在这里我也吧代码放上去。

 

算法详情（最优装载）：  有一批集装箱要装上一艘载重量为的轮船，已知集装箱的重量为wi（0<i<=n），最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

 

贪心策略：采用重量最轻者优先装入的贪心策略。

所以题目就很简单了，先按照重量排序，之后就从小到大选择箱子就行，直到船放不为止。

 

放上一道例题

 

 

 

下面放上代码

 

#include<iostream> 
#include <algorithm>
 using   namespace   std;
  struct   good{
      int   num;
      int  good_w= 0  ;
      bool  flag= false  ;
};
good goods[  100  ];

  int   max_loading ;
  bool   cmp(good a,good b){
      return  a.good_w< b.good_w;
}

  int  Process( int   n){
      for ( int  i= 0 ;i<n;i++ ){
          if (goods[i].good_w< max_loading){
            goods[i].flag = true  ;
            max_loading =max_loading- goods[i].good_w;
        }
    }
}

  bool   cmp_sec(good a,good b){
      return  a.num< b.num;
}
  int   main(){
      int   n;
    cin >> n;

    cin >> max_loading;
      for ( int  i= 0 ;i<n;i++ ) {
        cin >> goods[i].good_w;
        goods[i].num =i+ 1  ;
        
    }
    sort(goods,goods + n,cmp);
    Process(n);
    
sort(goods,goods + n,cmp_sec);
      for ( int  h= 0 ;h<n;h++ ){
        cout <<goods[h].flag<< "   "  ;
    }
}  

这里的解决问题的算法比解决一般问题要复杂一些，因为我这里在最后的时候将

 

  最后的结果用集合的形式来表示了。

所以我就需要用结构体去处理这个问题，并且要sort两次。

 

结果：

 

 

 

 

算法详情（背包问题）： 给定 n 个物品和一个容量为 C 的背包，物品 i 的重量是 Wi, 其价值为 Vi, 背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大，与 0-1 背包的区别是，在完全背包问题中，可以将物品的一部分装入背包，但不能重复装入。

设计算法的思路很简单，计算物品的单位价值，然后尽可能多的将单位重量价值高的物品放入背包中。

 

 

  代码详解：

这里放上计蒜课的　　HOMEWORK   https://nanti.jisuanke.com/t/328

 

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
struct work{
	double time;
	double value;
}works[1000];
bool cmp(work a,work b){

	return (a.value/a.time)>(b.value/b.time) ;
}
using namespace std;
int main(){
	while(1){
	
	int num;
	int all_time;
	
	cin>>num>>all_time;
	if(num==0&&all_time==0) exit(0);
	for(int i=0;i<num;i++){
		cin>>works[i].time>>works[i].value;
		
	}

	sort(works,works+num,cmp);
	int rest_time=all_time;
	double value=0;

	for(int n=0;n<num;n++){
		if(works[n].time<=rest_time) {
			value+=works[n].value;
			rest_time = rest_time-works[n].time;

		}
		else{
			double s = works[n].value/works[n].time;

			value+=rest_time*s;
			break;
		}
	}

	printf("%.2f\n",value);}
}

　　

 

这两个算法不算难，还是多做题目吧。

——————————————————————————————————————————————---Made By Pinging

查看更多关于算法复习周------“贪心问题之‘最优装载与背包问题’”的详细内容...