分数背包问题
背包问题是指给定一组物品，分别包含重量和利润值，需要确定要放入背包的物品子集，使得所有物品的总重量不超过背包的极限，且总利润值最大。
这是最常见的贪婪算法求解问题之一。它被称为分数背包问题。
为了更容易地解释这个问题，假设一个测试有12道题，每道10分，只需回答其中10道题就能获得满分100分。考生现在必须计算出最有优势的题目——也就是他有信心的题目——才能获得满分。但是，他不能全部回答12道题，因为这些题目不会获得任何额外的分数。这是背包问题最基本的实际应用。
背包算法
分数背包算法的输入是待添加到背包中的物品的权重 (Wi) 和利润值 (Pi)，输出是不超过限制且利润最大的物品子集。
算法
考虑所有物品，并分别列出它们的权重和利润。
计算所有物品的 Pi/Wi，并根据它们的 Pi/Wi 值按降序排列。
在不超过限制的情况下，将物品添加到背包。
如果背包还能容纳一定重量，但其他物品的重量超过了限制，则可以添加下次的小数部分。
因此，该问题被称为分数背包问题。
示例
对于给定的物品集合和 10 公斤的背包容量，找出要添加到背包中的物品子集，使得利润最大。
| Items | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Weights (in kg) | 3 | 3 | 2 | 5 | 1 |
| Profits | 10 | 15 | 10 | 12 | 8 |
解决方案
步骤 1
已知 n = 5
Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}
计算所有商品的 Pi/Wi
| Items | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Weights (in kg) | 3 | 3 | 2 | 5 | 1 |
| Profits | 10 | 15 | 10 | 20 | 8 |
| Pi/Wi | 3.3 | 5 | 5 | 4 | 8 |
步骤 2
根据 Pi/Wi 的降序排列所有项目
| Items | 5 | 2 | 3 | 4 | 1 |
|---|---|---|---|---|---|
| Weights (in kg) | 1 | 3 | 2 | 5 | 3 |
| Profits | 8 | 15 | 10 | 20 | 10 |
| Pi/Wi | 8 | 5 | 5 | 4 | 3.3 |
步骤 3
在不超过背包容量的情况下，将利润最高的物品放入背包。
背包 = {5, 2, 3}
然而，背包仍然可以承受 4 公斤的重量，但下一个 5 公斤的物品将超出容量。因此，5 公斤中的 4 公斤重量将放入背包。
| Items | 5 | 2 | 3 | 4 | 1 |
|---|---|---|---|---|---|
| Weights (in kg) | 1 | 3 | 2 | 5 | 3 |
| Profits | 8 | 15 | 10 | 20 | 10 |
| Knapsack | 1 | 1 | 1 | 4/5 | 0 |
因此，背包中的重量 = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10，最大利润为 [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 37。
示例
以下是使用贪婪方法的分数背包算法的最终实现 −
#include <stdio.h>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
int main(){
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
printf("Added object %d (%d, %d) completely in the bag. Space left: %d.
", maxi + 1, w[maxi], p[maxi], cur_w);
else {
printf("Added %d%% (%d, %d) of object %d in the bag.
", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi], p[maxi], maxi + 1);
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
}
}
printf("Filled the bag with objects worth %.2f.
", tot_v);
return 0;
}
输出
Added object 5 (8, 1) completely in the bag. Space left: 9. Added object 2 (15, 3) completely in the bag. Space left: 6. Added object 3 (10, 2) completely in the bag. Space left: 4. Added object 1 (10, 3) completely in the bag. Space left: 1. Added 19% (12, 5) of object 4 in the bag. Filled the bag with objects worth 45.40.
#include <iostream>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
int main(){
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
printf("Added object %d (%d, %d) completely in the bag. Space left: %d.
", maxi + 1, w[maxi], p[maxi], cur_w);
else {
printf("Added %d%% (%d, %d) of object %d in the bag.
", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi], p[maxi], maxi + 1);
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
}
}
printf("Filled the bag with objects worth %.2f.
", tot_v);
return 0;
}
输出
Added object 5 (8, 1) completely in the bag. Space left: 9. Added object 2 (15, 3) completely in the bag. Space left: 6. Added object 3 (10, 2) completely in the bag. Space left: 4. Added object 1 (10, 3) completely in the bag. Space left: 1. Added 19% (12, 5) of object 4 in the bag. Filled the bag with objects worth 45.40.
public class Main {
static int n = 5;
static int p[] = {3, 3, 2, 5, 1};
static int w[] = {10, 15, 10, 12, 8};
static int W = 10;
public static void main(String args[]) {
int cur_w;
float tot_v = 0;
int i, maxi;
int used[] = new int[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
System.out.println("Added object " + maxi + 1 + " (" + w[maxi] + "," + p[maxi] + ") completely in the bag. Space left: " + cur_w);
else {
System.out.println("Added " + ((int)((1 + (float)cur_w/p[maxi]) * 100)) + "% (" + w[maxi] + "," + p[maxi] + ") of object " + (maxi + 1) + " in the bag.");
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
}
}
System.out.println("Filled the bag with objects worth " + tot_v);
}
}
输出
Added object 41 (8,1) completely in the bag. Space left: 9 Added object 11 (15,3) completely in the bag. Space left: 6 Added object 21 (10,2) completely in the bag. Space left: 4 Added object 01 (10,3) completely in the bag. Space left: 1 Added 19% (12,5) of object 4 in the bag. Filled the bag with objects worth 45.4
n = 5
p = [3, 3, 2, 5, 1]
w = [10, 15, 10, 12, 8]
W = 10
cur_w = W
tot_v = 0
used = [0] * 10
for i in range(n):
used[i] = 0
while cur_w > 0:
maxi = -1
for i in range(n):
if (used[i] == 0) and ((maxi == -1) or ((w[i] / p[i]) > (w[maxi] / p[maxi]))):
maxi = i
used[maxi] = 1
cur_w -= p[maxi]
tot_v += w[maxi]
if cur_w >= 0:
print(f"Added object {maxi + 1} ({w[maxi]}, {p[maxi]}) completely in the bag. Space left: {cur_w}.")
else:
percent_added = int((1 + (cur_w / p[maxi])) * 100)
print(f"Added {percent_added}% ({w[maxi]}, {p[maxi]}) of object {maxi + 1} in the bag.")
tot_v -= w[maxi]
tot_v += (1 + (cur_w / p[maxi])) * w[maxi]
print(f"Filled the bag with objects worth {tot_v:.2f}.")
输出
Added object 5 (8, 1) completely in the bag. Space left: 9. Added object 2 (15, 3) completely in the bag. Space left: 6. Added object 3 (10, 2) completely in the bag. Space left: 4. Added object 1 (10, 3) completely in the bag. Space left: 1. Added 19% (12, 5) of object 4 in the bag. Filled the bag with objects worth 45.40.
应用
背包问题在现实世界中的许多应用中，只有少数是 −
在不损失太多材料的情况下切割原材料
挑选投资和投资组合
选择资产证券化的资产
为 Merkle-Hellman 算法生成密钥
认知无线电网络
功率分配
移动节点的网络选择
合作无线通信
