背包問題 小灰

Prerequisites: Algorithm for fractional knapsack problem

先決條件： 分數背包問題算法

Here, we are discussing the practical implementation of the fractional knapsack problem. It can be solved using the greedy approach and in fractional knapsack problem, we can break items i.e we can take a fraction of an item. For examples, you can read this article first.

在這里，我們正在討論小背包問題的實際實現 。 可以使用貪婪方法解決該問題，在小背包問題中，我們可以破壞物品，即可以取物品的一小部分。 例如，您可以先閱讀本文 。

Problem statement: We have given items i₁, i₂, ..., i_n (item we want to put in our bag) with associated weights w₁, w₂, ..., w_n and profit values P₁ , P₂ ,..., P_n. Now problem is how we can maximize the total benefit given capacity of bag is C?

問題陳述：我們給了項目i ₁ ， i ₂ ，...， i _n (我們要放入袋中的項目)，其權重為w ₁ ， w ₂ ，...， w _n和利潤值P ₁ ， P ₂ ，...， P _n 。 現在的問題是，在袋子容量為C的情況下， 如何才能使總收益最大化 ？

Algorithm:

算法：

1. Compute the profit per weight density for each item using the formula d_i = P_i / w_i.

   使用公式d _i = P _i / w _i計算每個項目的每重量密度利潤。

2. Sort each item by its profit per weight density.

   按每重量密度的利潤對每個項目進行排序。

3. Maximize the profit i.e Take as much as possible of the profit per weight density item not already in the bag.

   最大化利潤，即盡可能多地利用袋中尚未存在的每重量密度物品的利潤。

分數背負問題的C ++實現 (C++ implementation of fractional knapsack problem)

#include <bits/stdc++.h> 
using namespace std; 
// Structure for an item
struct myItem 
{
int itemNo; 
int profit;
int weight;
float ppw; // profit per weight
}; 
// Comparison function to sort Item according to profit per weight ratio
bool cmp(struct myItem a, struct myItem b) 
{ 
return a.ppw > b.ppw; 
} 
float fractionalKnapsack(int Capacity, struct myItem arr[], int n) 
{ 
//calculating profit per weight ratio
for(int i=0;i<n;i++)
{
arr[i].ppw = ((float)arr[i].profit / arr[i].weight);
}
// sorting Item on basis of profit per weight ratio 
sort(arr, arr + n, cmp); 
cout<<"details of all items : \n";
cout<<"itemNo\t"<<"Profit\t"<<"Weight\t"<<"PPW\t"<<endl;
for (int i = 0; i < n; i++) 
{ 
cout <<arr[i].itemNo<<"\t"<<arr[i].profit<<"\t"<<arr[i].weight<<"\t"<<((float)arr[i].ppw)<<endl; 
}
cout<<endl;
float Max = 0.0; // Maximum profit
int i=0; 
//take items until capacity becomes zero
while(Capacity > 0 && i<=n-1)
{
// if we can take all weights of item
if(Capacity >= arr[i].weight)
{
Max = Max + (float)arr[i].profit;
Capacity = Capacity - arr[i].weight;
}
// we can take only fraction of item
else
{
Max += (Capacity * arr[i].ppw);
Capacity = 0;
}
i++;
}  
return Max; 
} 
// driver function
int main() 
{ 
int C = 25;   //    Capacity of knapsack 
myItem arr[] = { {1, 30, 10, 0}, {2, 20, 5, 0} , {3, 40, 15, 0}, {4, 36, 8, 0}}; 
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"details of all items before sorting and without calculating PPW: \n";
cout<<"itemNo\t"<<"Profit\t"<<"Weight\t"<<"PPW\t"<<endl;
for (int i = 0; i < n; i++) 
{ 
cout <<arr[i].itemNo<<"\t"<<arr[i].profit<<"\t"<<arr[i].weight<<"\t"<<((float)arr[i].ppw)<<endl; 
} 
cout<<endl;
cout << "Maximum profit we can obtain = "<< fractionalKnapsack(C, arr, n);
return 0; 
} 

Output

輸出量

details of all items before sorting and without calculating PPW:
itemNo  Profit  Weight  PPW
1       30      10      0
2       20      5       0
3       40      15      0
4       36      8       0
details of all items :
itemNo  Profit  Weight  PPW
4       36      8       4.5
2       20      5       4
1       30      10      3
3       40      15      2.66667
Maximum profit we can obtain = 91.3333

翻譯自: https://www.includehelp.com/icp/fractional-knapsack-problem.aspx

背包問題 小灰