因为这两个算法均属于贪心算法里面的简单算法，所以我把他们写到了一起，这两道题目因为很好理解所以机考的可能也很大，所以在这里我也吧代码放上去。
?
算法详情（最优装载）：? 有一批集装箱要装上一艘载重量为的轮船，已知集装箱的重量为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测试数据/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
查看更多关于算法复习周------“贪心问题之‘最优装载与背包问题’”的详细内容...