贪心算法

7-17 部分背包

给定 N 种物品和一个背包。物品 i 的重量是 W i ,价值为 V i ;背包的容量为 V。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品,对每种物品可以选择:全部装入或装入部分,且不能重复装入。输入数据的第一行分别为:背包的容量 V,物品的个数 N。接下来的 N 行表示 N 个物品的重量和价值。输出为最大的总价值。

输入格式:

第一行连个整数,分别是V和N(<=1000) 接下来N行,每行分别为 W i 和 V i

输出格式:

输出为最大的总价值(保留两位小数)

输入样例:

1
2
3
4
5
15 4
3 5
4 6
5 7
7 12

输出样例:

1
24.40

EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
int v,n;
double maxx=0.0;
cin>>v>>n;
double shangpin[n][3];
for(int i=0;i<n;i++){
cin>>shangpin[i][0]>>shangpin[i][1];
shangpin[i][2]=shangpin[i][1]/shangpin[i][0];
//cout<<shangpin[i][2];
}
for(int i=0;i<n;i++){
int max=i;
for(int j=i+1;j<n;j++){
if(shangpin[j][2]>shangpin[max][2]){
max=j;
}
}
double temp0,temp1,temp2;
temp0=shangpin[i][0];
temp1=shangpin[i][1];
temp2=shangpin[i][2];
shangpin[i][0]=shangpin[max][0];
shangpin[i][1]=shangpin[max][1];
shangpin[i][2]=shangpin[max][2];
shangpin[max][0]=temp0;
shangpin[max][1]=temp1;
shangpin[max][2]=temp2;
}
for(int i=0;i<n;i++){
if(shangpin[i][0]<v){
maxx+=shangpin[i][1];
v-=shangpin[i][0];
}
else{
maxx+=shangpin[i][2]*v;
}
}
printf("%.2lf",maxx);
}

7-18 活动安排(贪心算法)

学校在最近几天有n个活动,这些活动都需要使用学校的大礼堂,在同一时间,礼堂只能被一个活动使用。由于有些活动时间上有冲突,学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出n个活动使用礼堂的起始时间begin**i和结束时间end**i(begin**i<end**i),请你帮助办公室人员安排一些活动来使用礼堂,要求安排的活动尽量多。

输入格式:

第一行一个整数n(n≤1000);

接下来的n行,每行两个整数,第一个begin**i,第二个是end**i(begin**i<end**i≤32767)。

输出格式:

输出最多能安排的活动个数。

输入样例:

1
2
3
4
5
6
5
12 18
5 11
5 30
15 23
2 28

输出样例:

1
2

EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;
class hd{
public:
int start;
int end;
};
int main(){
int n;
cin>>n;
hd a[n];
for(int i=0;i<n;i++){
cin>>a[i].start>>a[i].end;
}
for(int j=0;j<n;j++){
int min=j;
for(int k=j+1;k<n;k++){
if(a[min].end>a[k].end){
min=k;
}
}
hd temp;
temp=a[j];
a[j]=a[min];
a[min]=temp;
}
// for(int j=0;j<n;j++){
// cout<<a[j].end<<endl;
// }
int num=0;
int now=0;
for(int j=0;j<n;j++){
if(a[j].start>now){
now=a[j].end;
num++;
}

}
cout<<num;
}

7-19 过河问题

一个月黑风高的夜晚,几个人在河的右岸,他们要到河的左岸去。由于只有一把手电筒,因此必须每次过两人回一人,速度由慢者决定,问过河所需最短时间。

输入格式:

输入t组数据,每组数据第1行输入n(<=1000),第2行输入n个数,表示每个人过河的时间(<1000的正数)。

输出格式:

输出t行数据,每行1个数,表示每组过河最少时间。

输入样例:

1
2
3
1
4
1 2 5 10

输出样例:

1
17

EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
int n;
int a[1005];
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
int sum=0;
while(n>3){
sum+=min(2*a[2]+a[1]+a[n],a[n-1]+a[1]*2+a[n]);
n-=2;
}
if(n==1) sum+=a[1];
if(n==2) sum+=a[2];
if(n==3) sum+=a[1]+a[2]+a[3];
cout<<sum<<endl;
}
return 0;
}

扫一扫,分享到微信

微信分享二维码

请我喝杯咖啡吧~

支付宝
微信