实验要求
理解贪心算法的原理及一般应用。
思考贪心算法和动态规划法的区别。
编程实现典型的贪心算法，并对算法进行验证分析。
二. 实验内容
1.分别用动态规划、贪心法实现0-1背包问题，并对算法结果、效率进行比较分析。
实例：设n=4，价值向量V={12,11,9,8}，重量向量为W={8,6,4,3}，背包承重量为B=13。
2.编程实现活动安排问题。（教材89页表4.1）
3.编程实现教材111页4.3。
三. 实验结果
（1）0-1背包问题[动态规划]
input: n=4， V={12,11,9,8}， W={8,6,4,3}， B=13。
伪代码表述
输入：物品数 n，价值数组 v[1..n]，重量数组 w[1..n]，背包容量 B
输出：最大价值及其对应物品集合
初始化二维数组 dp[0..n][0..B] 为 0
for i 从 1 到 n:
for j 从 1 到 B:
if j < w[i]:
dp[i][j] ← dp[i-1][j]
else:
dp[i][j] ← max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
输出 dp[n][B]
j ← B
for i 从 n 递减到 1:
if dp[i][j] > dp[i-1][j]:
输出物品 i 的价值与重量
j ← j - w[i]源代码
// 动态规划实现0-1背包问题
// n=4,价值向量V={12,11,9,8}，重量向量为W={8,6,4,3}，背包承重量为B=13。
#include<bits/stdc++.h>
#define il inline
using namespace std;
#define pb push_back
#define fastio \
ios::sync_with_stdio(false); \
cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll N = 5e5+5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
const double PI = 3.1415926;
il void solve(){
int n = 4;
vector<int> v = {12, 11, 9, 8};
vector<int> w = {8, 6, 4, 3};
const int b = 13;
vector<vector<int>> dp(n+1, vector<int>(b+1, 0));
for (int i = 1; i <= n;++i)
{
for (int j = 1; j <= b;++j)
{
// 剩余重量比当前物品重量还小，只能不装入背包
if(j < w[i-1]){
dp[i][j] = dp[i - 1][j];
}else{
// 装入背包或不装入背包
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
}
}
}
cout << dp[n][b] << '\n';
int j = b;
for (int i = n; i > 0;--i)
{
if (dp[i][j] > dp[i-1][j])
{
cout << "选择物品:" << i << " 价值:" << v[i-1] << " 重量:" << w[i-1] << '\n';
j -= w[i-1];
}
}
}
int main()
{
fastio
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}运行结果
（2）0-1背包问题[贪心法] （是否对所有实例都能得到最优解？）
不是最优的,常见反例：价值/重量比高但重量大，贪心会选它导致剩余容量浪费
伪代码表述
输入：物品数 n，价值数组 v[1..n]，重量数组 w[1..n]，背包容量 B
输出：按单位价值贪心选取的总价值和物品集合
构造列表 ratio_list：
对每个物品 i：
ratio ← v[i] / w[i] // 单位价值
将 (ratio, i) 插入 ratio_list
按 ratio 从大到小对 ratio_list 排序
ans ← 0
wsum ← B
for (ratio, i) ∈ ratio_list:
if wsum ≥ w[i]:
ans ← ans + v[i]
wsum ← wsum - w[i]
输出 ans
wsum ← B
for (ratio, i) ∈ ratio_list:
if wsum ≥ w[i]:
输出 “选择物品 i，价值 v[i]，重量 w[i]”
wsum ← wsum - w[i]源代码
// 贪心算法实现0-1背包问题
// n=4,价值向量V={12,11,9,8}，重量向量为W={8,6,4,3}，背包承重量为B=13。
#include<bits/stdc++.h>
#define il inline
using namespace std;
#define pb push_back
#define fastio \
ios::sync_with_stdio(false); \
cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll N = 5e5+5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
const double PI = 3.1415926;
il void solve(){
int n = 4;
vector<int> v = {12, 11, 9, 8};
vector<int> w = {8, 6, 4, 3};
const int b = 13;
map<double, int, greater<int>> mp; //降序
for (int i = 0; i < n;++i)
mp.insert({1.0 * v[i]/w[i], i});
int ans = 0;
int wsum = b;
for (auto it = mp.begin(); it != mp.end();++it)
{
if (wsum >= w[it->second])
{
ans += v[it->second];
wsum -= w[it->second];
}
}
cout << ans << '\n';
wsum = b;
for (auto it = mp.begin(); it != mp.end();++it)
{
if (wsum >= w[it->second])
{
cout << "选择物品:" << it->second + 1 << " 价值:" << v[it->second] << " 重量:" << w[it->second] << '\n';
wsum -= w[it->second];
}
}
}
int main()
{
fastio
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}运行结果
活动安排问题
源代码
// 贪心算法实现活动安排问题
#include<bits/stdc++.h>
#define il inline
using namespace std;
#define pb push_back
#define fastio \
ios::sync_with_stdio(false); \
cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll N = 5e5+5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
const double PI = 3.1415926;
typedef struct{
int start;
int finish;
}Activity;
vector<Activity> activities = {
{0, 0}, // 占位不起作用
{1, 4},
{3, 5},
{2, 6},
{5, 7},
{4, 9},
{5, 9},
{6, 10},
{8, 11},
{8, 12},
{2, 13},
};
il void solve(){
vector<int> ans;
ans.pb(1);
int j = 1;
for (int i = 2; i < activities.size();++i)
{
if(activities[i].start >= activities[j].finish)
{
ans.pb(i);
j = i;
}
}
cout << "选择的活动: ";
for (int i = 0; i < ans.size();++i)
{
cout << ans[i] << " ";
}
cout << '\n';
}
int main()
{
fastio
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}运行结果
- 找基站位置，并且使得基站总数达到最少。
伪代码表述
i ← 1, ans ← []
while i ≤ n:
start ← d[i]
station ← start + 4
把 station 加入 ans
while i ≤ n 且 d[i] ≤ station + 4:
i ← i + 1源代码
// 找基站位置，并且使得基站总数达到最少。
#include<bits/stdc++.h>
#define il inline
using namespace std;
#define pb push_back
#define fastio \
ios::sync_with_stdio(false); \
cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll N = 5e5+5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
const double PI = 3.1415926;
vector<int> distance_a = {4, 5, 8, 12, 14, 15, 16, 18, 20, 22,30};
il void solve(){
int i = 1;
vector<int> ans;
int n = distance_a.size() - 1;
while(i <= n)
{
int start = distance_a[i];
int station = start + 4;
ans.pb(station);
while (i <= n && distance_a[i] <= station + 4)
++i;
}
// 输出选择的基站的位置
cout << "基站位置: ";
for (int i = 0; i < ans.size();++i)
{
cout << ans[i] << " ";
}
cout << '\n';
}
int main()
{
fastio
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}运行结果
vector<int> distance_a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10};
vector<int> distance_a = {4, 5, 8, 12, 14, 15, 16, 18, 20,22,30};
