資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式解決分數揹包問題
在分數揹包問題中，給定了一組物品，每個物品都具有重量和價值。我們需要打破物品以最大化揹包的總價值，這可以透過貪婪演算法來完成。
演算法
Begin Take an array of structure Item Declare value, weight, knapsack weight and density Calculate density=value/weight for each item Sorting the items array on the order of decreasing density We add values from the top of the array to total value until the bag is full, i.e; total value <= W End
示例程式碼
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct {
int v;
int w;
float d;
} Item;
void input(Item items[],int sizeOfItems) {
cout << "Enter total "<< sizeOfItems <<" item's values and weight" <<
endl;
for(int i = 0; i < sizeOfItems; i++) {
cout << "Enter "<< i+1 << " V ";
cin >> items[i].v;
cout << "Enter "<< i+1 << " W ";
cin >> items[i].w;
}
}
void display(Item items[], int sizeOfItems) {
int i;
cout << "values: ";
for(i = 0; i < sizeOfItems; i++) {
cout << items[i].v << "\t";
}
cout << endl << "weight: ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].w << "\t";
}
cout << endl;
}
bool compare(Item i1, Item i2) {
return (i1.d > i2.d);
}
float knapsack(Item items[], int sizeOfItems, int W) {
int i, j;
float totalValue = 0, totalWeight = 0;
for (i = 0; i < sizeOfItems; i++) {
items[i].d = (float)items[i].v / items[i].w; //typecasting done (v is int and w is also int so we get final value of d as int)
}
sort(items, items+sizeOfItems, compare);
/*
uncomment if u need to check the data after sortingis done
cout << "values : ";
for(i = 0; i < sizeOfItems; i++) {
cout << items[i].v << "\t";
}
cout << endl << "weights: ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].w << "\t";
}
cout << endl << "ratio : ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].d << "\t";
}
cout << endl;
*/
for(i=0; i<sizeOfItems; i++) {
if(totalWeight + items[i].w<= W) {
totalValue += items[i].v ;
totalWeight += items[i].w;
} else {
int wt = W-totalWeight;
totalValue += (wt * items[i].d);
totalWeight += wt;
break;
}
}
cout << "Total weight in bag " << totalWeight<<endl;
return totalValue;
}
int main() {
int W;
Item items[4];
input(items, 4);
cout << "Entered data \n";
display(items,4);
cout<< "Enter Knapsack weight \n";
cin >> W;
float mxVal = knapsack(items, 4, W);
cout << "Max value for "<< W <<" weight is "<< mxVal;
}輸出
Enter total 4 item's values and weight Enter 1 V Enter 1 W Enter 2 V Enter 2 W Enter 3 V Enter 3 W Enter 4 V Enter 4 W Entered data values: 2 0 0 0 weight: 0 490642064 0 4196544 Enter Knapsack weight Total weight in bag 0 Max value for 0 weight is 2
更新於：17-2-2022
6 千次瀏覽
廣告