분할가능 배낭 문제(Fractional Knapsack Problem)-C++

Knapsack Problem(배낭문제)

1)Fractional Knapsack Problem

1. 보석의 무게를 쪼갤 수 있다는 가정을 둔다.
2. 예를 들어 보석이 10kg라도 내가 들고가고싶은 만큼 담아서 가방에 넣을 수 있다.

->greedy를 이용해서 해결

2)0-1 Knapsack Problem

1. 보석의 무게를 쪼 갤 수없다.
2. 예를 들어 보석이 10kg라면 10kg 그대로 가방에 담아야 한다.

->dynamic programming을 이용해서 해결

 

배낭문제의 목표는 가방에 담는 보석들의 가치 합이 최대가 되야한다.

 

●Greedy Approach 

1. 탐욕법을 통한 전략은 다음과 같다.
2. 단위 무게당 가치가 가장 큰 보석을 담는다.
3. 가방에 최대 무게가 넘지않을때까지 보석을 담는다.

이러한 접근법은 보석을 쪼갤수있는 배낭문제는 풀 수있지만, 보석을 쪼갤수 없는 배낭문제는 풀 수없다.

 

아래 그림은 0-1 Knapsack Problem이다.

탐욕적으로 접근한다면 단위무게가 많은 5kg를 담고 그 다음 순서인 20kg를 담게 된다. 그 다음 10kg를 선택하지만 가방의 남은 무게가 10kg보다 적어 가방에는 10kg의 보석을 담지 못한다.

 

즉 탐욕적으로 접근하면 가방의 용량을 낭비하는 현상이 생긴다.

 

보석의 무게를 쪼갤 수 있는 Fractional Knapsack Problem에 탐욕법을 적용하면 어떻게 될까?

탐욕적으로 접근하면 가방에 담긴 보석의 가치가 최대값이 되는 결과를 도출할 수 있다.

---

이번 글에서는 Fraction Knapsack problem을 Greedy하게 풀것이다.

 

☆설계

1. 담는 보석들의 무게 합은 가방의 무게를 넘으면 안된다.
2. 보석들의 perweight를 구하고 perweight 내림차순으로 정렬한다.
3. 보석을 담고 가방무게를 비교하고, 만약 보석의 무게가 가방의 잔여 무게보다 무겁다면 보석을 분할해서 넣는다.
4. 가방에 담는 보석과 보석의 무게, 무게합 출력한다.

★구현

• 구조체 선언 및, 전역변수 ,함수 선언

#include <iostream>
#include <vector>

using namespace std;
typedef struct bag {
	int weight; //보석의 무게
	int profit; //보석의 가치
	int perweight; //보석의 단위 무게당 가치
}bag;
int n, t, lim,Max,total;
vector<bag>bagvector; 
vector<bag>knap;
void knapsack(vector<bag>&knap, int& maxprofit, int& totweight,bag *c);

• 보석의 무게, 가치, 단위무게당 가치 입력받기

	cin >> n;
	bag* b = new bag[n];
	bag* c = new bag[n];
	vector<int>weight;
	vector<int>profit;
	for (int i = 0; i < n; i++)
	{
		int w;
		cin >> w;
		weight.push_back(w);
	}
	for (int i = 0; i < n; i++)
	{
		int p;
		cin >> p;
		profit.push_back(p);
	}
	int i = 0;
	for (int i = 0; i<n; i++)
	{		
		if (weight[i] == 0 || profit[i] == 0) //보석의 무게가 0이거나 가치가 0일때는 무시함.
		{
			continue;
		}
		else {
			b[i].weight = weight[i];
			b[i].profit = profit[i];
			b[i].perweight = profit[i] / weight[i];
			knap.push_back(b[i]);
		}
	}

문제 조건 때매 너무 지저분하게 짠 것같다. 아직 코딩 스킬이 부족해서 그런  것같다. ㅠㅠ

처음에는 바로 구조체에 넣어줬는데 만약 보석의 무게가 0 이거나 가치가 0 일때의 경우를 무시해야하는데 그럴 경우 구조체의 쓰레기값이 들어가는 경우가 생겨서 구조체 배열로 짰는데, 조금 더 고민을 해봐야 할 것같다..!

• 보석을 perwegiht로 내림차순 정렬하기

for (int i = 0; i < knap.size(); i++)
	{
		for (int j = i + 1; j <knap.size(); j++)
		{
			if (knap[i].perweight < knap[j].perweight)
			{
				swap(knap[i], knap[j]);
			}
		}
	}

• 가방의 보석 담기 - Knapsack함수

//b와 c는 가방에 담는 보석의 무게와 가치를 저장.  maxprofit은 가방에 담는 보석의 가치합,
//totweight는 현재 가방에 담긴 보석의 무게
void knapsack(vector<bag>&b,int &maxprofit,int &totweight,bag *c)
{
	maxprofit = totweight = 0;
	for (int i = 0; i < b.size(); i++)
	{
		if (totweight + b[i].weight <= lim) {//꽉찰때까지 계속넣는다
			maxprofit += b[i].profit;
			totweight += b[i].weight;
			c[i].profit = b[i].profit;
			c[i].weight = b[i].weight;
			bagvector.push_back(c[i]);
		}
		else
		{
			c[i].profit = (lim - totweight) * b[i].perweight;
			c[i].weight = (lim - totweight);
			bagvector.push_back(c[i]);
			maxprofit += (lim - totweight) * b[i].perweight;
			totweight += (lim - totweight);
			break;
		}
	}
}

1. if문은 보석의 무게가 가방의 잔여무게를 넘지 않을때이다.
2. 그럴 경우에는 보석을 분할없이 그대로 넣어주면된다.
3. 하지만 만약 보석의 무게와 현재 가방의 잔여무게가 가방의 최대무게를 넘게 되는경우 else문이 실행된다.
4. 최대무게에서 들어갈수있을만큼 보석을 담고 그 단위무게를 곱해주면 가방의 용량을 낭비 없이 꽉 채울 수있다.

하지만 이렇게 짠 경우에 계속 오류가 발생했다. 

오류의 이유는 간단했다.

만약 가방의 최대 무게가 7kg이고 보석을 2kg,5kg담았을 때 totwegiht+b[i].weight는 limt보다 커지므로 

else문에 들어가게된다. 하지만 이미 totwegiht 는 lim과 같기 때문에

구조체 c에 무게와 가치는 0,0이 들어가게되는것이다!!!

따라서 분할해서 넣을 필요가 없을 때도 고려해야하기때문에 0인지 아닌지에 대한 검사가 필요하다.

if (c[i].profit != 0 && c[i].weight != 0)
	bagvector.push_back(c[i]);

 

• 최종코드

#include <iostream>
#include <vector>
using namespace std;
typedef struct bag
{
    int weight;
    int profit;
    int perweight;
    int id;
} bag;
int n, t, lim, Max, total;
vector<bag> bagvector;
vector<bag> knap;
void knapsack(vector<bag> &knap, int &maxprofit, int &totweight, bag *c);
int main()
{

    cin >> n;
    bag *b = new bag[n];
    bag *c = new bag[n];
    vector<int> weight;
    vector<int> profit;
    for (int i = 0; i < n; i++)
    {
        int w;
        cin >> w;
        weight.push_back(w);
    }
    for (int i = 0; i < n; i++)
    {
        int p;
        cin >> p;
        profit.push_back(p);
    }
    int i = 0;
    for (int i = 0; i < n; i++)
    {
        if (weight[i] == 0 || profit[i] == 0)
        {
            continue;
        }
        else
        {
            b[i].weight = weight[i];
            b[i].profit = profit[i];
            b[i].perweight = profit[i] / weight[i];
            knap.push_back(b[i]);
        }
    }
    for (int i = 0; i < knap.size(); i++) //단위무게가 무거운 순으로 정렬함.(내림차순 정렬) 
    {
        for (int j = i + 1; j < knap.size(); j++)
        {
            if (knap[i].perweight < knap[j].perweight)
            {
                swap(knap[i], knap[j]);
            }
        }
    }
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> lim; //제한무게
        knapsack(knap, Max, total, c);
        cout << Max << "\n";
        for (int j = 0; j < bagvector.size(); j++)
        {
            if (i == t - 1 && j == bagvector.size() - 1)
                cout << bagvector[i].weight << " " << bagvector[j].profit;
            else
                cout << bagvector[j].weight << " " << bagvector[j].profit << "\n";
        }
        bagvector.resize(0);
    }
}
void knapsack(vector<bag> &b, int &maxprofit, int &totweight, bag *c)
{
    maxprofit = totweight = 0;
    for (int i = 0; i < b.size(); i++)
    {
        if (totweight + b[i].weight <= lim) //내가 다음 물건을 넣어도 지장이 없을때.
        { //꽉찰때까지 계속넣는다
            maxprofit += b[i].profit;
            totweight += b[i].weight;
            c[i].profit = b[i].profit;
            c[i].weight = b[i].weight;
            bagvector.push_back(c[i]);
        }
        else //만약 내가 다음에 넣을려고 하는데 가방무게가 초과된다면 쪼개야함.
        {
            c[i].profit = (lim - totweight) * b[i].perweight;
            c[i].weight = (lim - totweight);
            if (c[i].profit != 0 && c[i].weight != 0) //
                bagvector.push_back(c[i]);
            maxprofit += (lim - totweight) * b[i].perweight;
            totweight += (lim - totweight);
            break;
        }
    }
}

---

👀정리

1. 단위당 무게가 무거운 순으로 정렬함.
2. 분할하지않고 내가 넣을 수 있을 때 까지 넣어줌.
   1. 만약 가방이 넘친다면 그 때 분할해서 넣어줌.