16.1 活动选择问题
1 问题提出
假定有一个
2 思路&伪代码
- 考虑目前能选择的活动，选择其中最早结束的活动，使它剩下的资源可供它之后尽量多的活动使用
2.1 递归贪心算法
s数组：活动开始时间f数组：活动结束时间- 下标
k：要求解的子问题S_k - 问题规模
n - 返回：
S_k的一个最大兼容活动集
Recursive_Activity_Selector(s,f,k,n)
m = k+1;
while m<=n and s[m]<f[k]
m = m+1
if m<=n
return {a_m} and Recursive_Activity_Selector(s,f,m,n)
else return ∅
2.2 迭代贪心算法
时间复杂度
s数组：活动开始时间f数组：活动结束时间- 下标
k：最近加入集合A的活动的下标 - 问题规模
n - 返回：
S_k的一个最大兼容活动集
Greedy_Activity_Selector(s,f)
n = s.length
A = {a1}
k = 1
for m=2 to n
if s[m] >= f[k]
A = A and {am}
k = m
return A
3 c语言实现（迭代贪心算法）
int n, ans[MAX], a[MAX], s[MAX], f[MAX];
void Greedy_Activity_Selector(){
ans[1] = a[1];
int lastId=1, ansNum = 1;
for(int i=2; i<=n; i++){
if(s[i] >= f[k]){
ansNum++;
ans[ansNum] = a[i];
lastId = i;
}
}
}
16.2 贪心算法原理
-
设计步骤
- 从动态规划出发
- 更直接的设计方法
- 从动态规划出发
-
贪心选择性质（greedy-choice property）：我们可以通过做出局部最优（贪心）选择来构造全局最优解。换句话说，当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。
-
最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。
-
贪心与动态规划
- 0-1背包问题：一个正在抢劫商店的小偷发现了
- 分数背包问题：设定与0-1背包问题是一样的，但对每个商品，小偷可以拿走其一部分，而不是只能做出二元(0-1)选择。
- 贪心策略能求解分数背包问题：我们首先计算每个商品的每磅价值
- 贪心策略不能求解0-1背包问题，0-1背包需要用动态规划求解：在0-1背包问题中，当我们考虑是否将一个商品装入背包时，必须比较包含此商品的解和不包含它的子问题的解
- 0-1背包问题：一个正在抢劫商店的小偷发现了
0-1背包 c++实现
一个正在抢劫商店的小偷发现了
二维dp
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, W, v[N], w[N], f[N][N];
int main(){
cin >> n >> W;
for (int i = 1; i <= n; ++i)cin >> v[i] >> w[i];
// f[0][0~m] = 0; 考虑0件物品，总体积不超过0~m的最大价值
// 由于此时一件物品都没有所以最大价值都0
// 由于之前在前面已经在全局变量中初始化过，所以此处不用再初始化
for (int i = 1; i <= n; i++){
for (int j = 0; j <= m; ++j){
f[i][j] = f[i - 1][j]; // 不选择当前物品时的价值，直接继承上一个状态的价值
// 如果当前背包容量可以放下当前物品，则尝试放入，更新最大价值
if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
一维dp
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, W, v[N], w[N], f[N];
int main(){
cin >> n >> W;
for (int i = 1; i <= n; ++i)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; ++i){ // 遍历所有物品
for (int j = m; j >= w[i]; j--){ // 逆序遍历背包容量
// 更新f[j]，即考虑放入当前物品i时的最大价值
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
cout << f[m] << endl;
return 0;
}
完全背包 c++实现
一个正在抢劫商店的小偷发现了
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, v[N], w[N], f[N];
int main(){
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; ++i){ // 遍历所有物品
for (int j = v[i]; j <= m; j--){ // 逆序遍历背包容量
// 更新f[j]，即考虑放入当前物品i时的最大价值
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
多重背包 c++实现
一个正在抢劫商店的小偷发现了
//二进制优化
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,V;
int v[MAXN],w[MAXN];
int f[MAXN];
int main(){
cin>>n>>V;
int cnt=0;//记录新的物体数
for(int i=1,a,b,s;i<=n;i++) {
cin>>a>>b>>s;
int k=1;
while(k<=s){//将每个物品都按照二进制合成
v[++cnt]=k*a;
w[cnt]=k*b;
s-=k;
k*=2;
}
if(s){
v[++cnt]=s*a;
w[cnt]=s*b;
}
}
for(int i=1;i<=cnt;i++)//01背包
for(int j=V;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[V];
return 0;
}
分数背包（部分背包） c实现
一个正在抢劫商店的小偷发现了
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct coin{
double m;// 重量
double v;// value
double rou;
};
int cmp(const void *a, const void *b){
struct coin *pa = (struct coin *)a;
struct coin *pb = (struct coin *)b;
if(pa->rou > pb->rou){
return -1;
}else{
return 1;
}
}
int main() {
int n;
double t;
scanf("%d%lf", &n, &t);
struct coin gold[110]={};
for(int i=0; i<n; i++){
scanf("%lf%lf", &gold[i].m, &gold[i].v);
gold[i].rou = gold[i].v / gold[i].m;
}
qsort(gold, n, sizeof(struct coin), cmp);
double ans=0;
int now=0;
while(t >= 0){
if(now == n){
break;
}
if(gold[now].m < t){
t -= gold[now].m;
ans += gold[now].v;
}else{
ans += gold[now].v * (t/gold[now].m);
t = 0;
break;
}
now++;
}
printf("%.2lf", ans);
return 0;
}
16.3 赫夫曼编码
1 问题提出
在本节中，我们考虑一种二进制字符编码(或简称编码)的方法，每个字符用一个唯一的二进制串表示，称为码字。如果使用定长编码，需要用3位来表示6个字符:a=000，b=001，…，f=101。这种方法需要300000个二进制位来编码文件。是否有更好的编码方案呢?
2 原理&伪代码
-
前缀码：没有任何码字是其他码字的前缀。
-
文件的最优编码方案总是对应一棵满(full)二叉树，即每个非叶结点都有两个孩子结点。因此可以说，若
-
代价：给定一棵对应前缀码的树
-
Huffman(C)
n = |C|
Q = C
for i=1 to n-1
allocate a ne node z
z.left = x = Extrac_Min(Q)
z.right = y = Extract_Min(Q)
z.freq = x.freq + y.freq
Insert(Q,z)
return Extract_Min(Q)
时间复杂度
3 c语言实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
// 结构体
typedef struct Node {
char data;
int frequency;
struct Node* left;
struct Node* right;
} Node;
// 创建新节点的函数
// return: 结构体指针类型
// data: 结构体的字符
// frequency: 字符的出现频率
Node* createNode(char data, int frequency) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->frequency = frequency;
node->left = NULL;
node->right = NULL;
return node;
}
// Huffman构建函数
Node* buildHuffmanTree(char* inputText) {
int charCount[256] = { 0 };
int length = strlen(inputText);
int i;
// 统计ascii码为i的字符的出现次数
for (i = 0; i < length; i++) {
charCount[(int)inputText[i]]++;
}
// 创建叶子结点
Node* nodes[256];
int nodeCount = 0;
for (i = 0; i < 256; i++) {
if (charCount[i] > 0) {
nodes[nodeCount] = createNode((char)i, charCount[i]);
nodeCount++;
}
}
// 依次合并叶子结点
while (nodeCount > 1) {
int minFrequency1 = length + 1; // 当前频率最小的
int minFrequency2 = length + 1; // 当前频率次小的
int index1 = -1;
int index2 = -1;
for (i = 0; i < nodeCount; i++) { // 获得minFrequency1和minFrequency2以及index1 index2
if (nodes[i]->frequency < minFrequency1) {
minFrequency2 = minFrequency1;
index2 = index1;
minFrequency1 = nodes[i]->frequency;
index1 = i;
} else if (nodes[i]->frequency < minFrequency2) {
minFrequency2 = nodes[i]->frequency;
index2 = i;
}
}
// 把最小的和次小的构建为一个树
Node* parent = createNode('\0', nodes[index1]->frequency + nodes[index2]->frequency);
parent->left = nodes[index1];
parent->right = nodes[index2];
// parent放进去，原孩子删掉，最后一个往前移，node数量--
nodes[index2] = parent;
nodes[index1] = nodes[nodeCount - 1];
nodeCount--;
}
return nodes[0];
}
// 编写huffman编码表及打印
void printHuffmanCodes(Node* root, int code[], int top, int codeTable[][256], int codeLengths[]) {
if (root->left) { // 有左子结点
code[top] = 0;
printHuffmanCodes(root->left, code, top + 1, codeTable, codeLengths);
}
if (root->right) { // 有右子节点
code[top] = 1;
printHuffmanCodes(root->right, code, top + 1, codeTable, codeLengths);
}
if (root->left == NULL && root->right == NULL) { // 是跟节点
codeLengths[(int)root->data] = top; // 字符root->data的编码长度为top
printf("%c:",root->data); // 输出字符root->data
for (int i = 0; i < top; i++) { // 输出字符root->data的编码
codeTable[(int)root->data][i] = code[i];
printf("%d",code[i]);
}
printf("\n");
}
}
// 编写编码函数
void encodeText(Node* root, char* inputText, char encodedText[], int codeTable[][256], int codeLengths[]) {
int length = strlen(inputText);
int i, j;
for (i = 0; i < length; i++) {
char character = inputText[i]; // 当前处理的字符
int length = codeLengths[(int)character]; // 字符转化成huffman编码后的长度
for (j = 0; j < length; j++) {
encodedText[strlen(encodedText)] = codeTable[(int)character][j] + '0';
}
}
}
// 编写解码函数
void decodeText(Node* root, char* encodedText, char* decodedText) {
int length = strlen(encodedText);
int i = 0;
while (i < length) {
Node* current = root;
while (current->left != NULL || current->right != NULL) {
if (encodedText[i] == '0') {
current = current->left;
} else if (encodedText[i] == '1') {
current = current->right;
}
i++;
}
decodedText[strlen(decodedText)] = current->data;
}
decodedText[strlen(decodedText)] = '\0';
}
int main() {
char inputText[MAX] = "";
gets(inputText);
Node* root = buildHuffmanTree(inputText);
int code[256];
int top = 0;
int codeTable[256][256] = {0};
int codeLengths[256] = {0};
printf("Huffman Codes:\n");
printHuffmanCodes(root, code, top, codeTable, codeLengths);
printf("\n");
printf("InputText:\n%s\n\n",inputText);
// 字符转huffman
char encodedText[1000] = "";
encodeText(root, inputText, encodedText, codeTable, codeLengths);
printf("Encoded Text: \n%s\n\n", encodedText);
// huffman转字符
char decodedText[1000] = "";
decodeText(root, encodedText, decodedText);
printf("Decoded Text: \n%s\n\n", decodedText);
return 0;
}
