Split knapsack problem (greedy algorithm)

Description:

There are n objects with different values v[i] and weights w[i] (if you select the object's w[i], you can get the value v[i]).

You have a container to pick them out. You can divide them into pieces of any size according to your needs. The maximum weight of objects that can be picked is given as w. Please calculate the maximum value you can get.

 

Input:

Input n W in the first line (0 < = n < = 1000) (0 < = w < = 10000)

Enter the value of n items in the second line (0 < = v [i] < 10000)

Enter the mass of n items in the third line (0 < = w [i] < 10000)

Output:

Maximum value, three decimal places reserved.

 

analysis:

This problem is different from the traditional 0-1 knapsack problem. The objects in this problem can be divided into any parts. Therefore, we can use greedy algorithm to solve the problem according to the cost performance (value / quality) of the items, and put the objects into the knapsack according to the cost performance. When the objects cannot be completely put into the knapsack, the total value = the value of the items completely put + the remaining space of the knapsack *Next, you should put the cost performance of backpack items.

 

code:

#include <iostream>
#include <algorithm>
#include<iomanip>
using namespace std;

//We need a structure that can find weight and value through cost performance.
//To make a ranking, we need to rank the cost performance ratio from high to bottom, and the weight and (value) in the process of ranking should correspond to each other

typedef struct {
    double aver;
    double w;
    double v;
}Knapsack;

bool cmp(Knapsack a, Knapsack b)
{
    return a.aver > b.aver;
}
int main()
{
    Knapsack arrays[1009];
    int n;
    double m;
    double V = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arrays[i].v;
    for (int i = 0; i < n; i++)
        cin >> arrays[i].w;


    //Cost performance
    for (int i = 0; i < n; i++)
    {
        arrays[i].aver = arrays[i].v / arrays[i].w;
        //cout << arrays[i].aver << endl;
    }

    //Cost performance ranking
    sort(arrays, arrays + n, cmp);
  
    int sum = 0;
    for (int i = 0; i < n; i++)  //When the backpack can hold all the items, directly output the sum of the values of all the items
    {
        sum += arrays[i].w;
    }
    if (sum < m)
    {
        for (int j = 0; j < n; j++)
            V += arrays[j].v;
          //V = floor(V * 1000.0) / 1000.0;
        cout << setiosflags(ios::fixed) << setprecision(3) << V << endl;
        return 0;
    }
    //It should be decided by the cost-effective order, through the capacity, to select the items to be loaded

    for (int i = 0; i < n; i++) {
        if (arrays[i].w <= m)
        {
            V = V + arrays[i].v;
            m = m - arrays[i].w;
        }
        else {//Directly transfer the remaining m Just join
            V = V + m * arrays[i].aver;
            m = 0;
        }
        if (m == 0)
            break;
    }
    //V = floor(V * 1000.0) / 1000.0;
    cout << setiosflags(ios::fixed) << setprecision(3) << V << endl;
    return 0;
}
 

Tags: iOS

Posted on Thu, 23 Apr 2020 08:31:15 -0700 by Isityou