ABOUT Vector index

vector - modify data

at : access specified element with bounds checking
operator[] : access specified element

vector <int> v;
for(int i=1;i<=10;i++){
   v.push_back(i);
}

v.at(4) = -1;
v[4] = 77;

• at and operator[] both return a reference to the indexed element

• you’d better take the habit to use at, less idiomatic, but bound-checking is priceless

• A much better way is to use at(...). This will automatically check for out of bounds behaviour and break throwing an std::out_of_range.

v.at(10) = 9;

• We will get:
  terminate called after throwing an instance of ‘std::out_of_range’ what(): vector::_M_range_check: __n (which is 10) >= this->size() (which is 4)

vector - erase : erase data

vector <int> v;
for(int i=1;i<=10;i++){
   v.push_back(i);
}

int count = 0;
for(vector<int>::iterator it = v.begin(); it != v.end(); it++){
    if(count == 5){ // in case of the index is 5 --> data will be erased
        it = v.erase(it);
        break;
    }else{
        count++;
    }
}

vector - insert : insert data

vector <int> v;
for(int i=1;i<=10;i++){
   v.push_back(i);
}

int count = 0;
for(std::vector<int>::iterator it = v.begin(); it != v.end(); it++){
    if(count == 5){// in case of the index is 5 --> data will be inserted
        v.insert(it,6);
        break;
    }else{
        count++;
    }
}

Fractional Knapsack Problem

• The problem of putting things in a backpack with a weight limit of k for maximum value
  • Each object can be expressed as weight (w) and value (v)
  • Since the object can be split, a part of the object can be put in a backpack, so it is called Fractional Knapsack Problem
    • In contrast to the Fractional Knapsack Problem, there is also a backpack problem in which objects cannot be split into pieces (called 0/1 Knapsack Problem)

C++

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

vector<pair<int, int>> data_list { {10,10}, {15,12}, {20,10}, {25,8},{30,5} };

bool compare(pair<int, int> a, pair<int, int> b)
{
	return (a.second/a.first) > (b.second/b.first); 
}

int main()
{
	float data_weight;
	cin >> data_weight;
	
	sort(data_list.begin(), data_list.end(), compare);
	
	float total_value = 0;
	float fraction = 0;
	for(auto it = data_list.begin(); it != data_list.end(); ++it)
	{
		if(data_weight - it->first >=0 )
		{
			data_weight -= it->first;
			total_value += it->second;
		}
		else
		{
			fraction = data_weight / it->first;
			total_value += (it->second * fraction);
			break;
		}
		
	}
	
	cout << total_value <<endl;
	cout << fraction <<endl;
	
	
	return 0;
}

1. What is the greed algorithm?

Problem solving method for getting a value close to the optimal solution
Whenever you need to decide between one of several cases, select the case that you think is the best every moment and get the final value
Selecting the best case for each step when there are multiple cases

2. Limitations of the greed algorithm

• The greed algorithm is used for approximation estimation
• Because it is not always possible to find the optimal solution
• It is one of the methods to find the value close to the optimal solution

• When starting finding the path from the root node to the leaf node for finding the largest value
  • 7-> 12-> 6 is selected when the Greedy algorithm is applied
    • so, 7 + 12 + 6 = 25
  • However, the actual largest value is 7 -> 3 -> 99
    • 7 + 3 + 99 = 109

3. Greedy Algorithm example

coin change problem

• When the value to be paid is 4720 won, pay the lowest number of coins with 1 won, 50 won, 100 won, and 500 won coins
  • It can be implemented by filling in the value that requires maximum payment from the largest coin
  • You can select the case that you think is optimal every moment with the greed algorithm

C++

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

bool compare(int a, int b)
{
	return a > b;
}
int main()
{
	int n;
	scanf("%d", &n);
	
	int answer = 0;
	int coins[] = {1, 100, 50, 500};
	int length = sizeof(coins)/sizeof(coins[0]);
	
	sort(coins, coins+4, compare);
	
	for(int i = 0; i < length; ++i)
	{
		int balance = n % coins[i];
		answer += (n/coins[i]);
		printf("%d %d %d \n", coins[i], n/coins[i], balance);
		n = balance;
	}
	
	printf("%d", answer);
	return 0;
}