---
title: algorithm VII
description: 第七次作業
---
# Group 2
組員:王承隆、賴文宏、施宗佑、王昱翔、王柏喬、莊淳方、傅文宗

# Problem 1
## Topic
Determine the cost and structure of an optimal binary search tree for a set of $n = 7$ keys with the following probabilities
## Solution

digraph Tree{
  k5->k2
  k5->k7
  k2->k1
  k2->k3
  k7->k6
  k3->k4
  
  k7->d7
  k1->d0
  k1->d1
  k3->d2
  k6->d5
  k6->d6
  k4->d3
  k4->d4
}

# Problem 2
[CLRS 3 rd ] Exercise 15.5-4
## Topic
Knuth [212] has shown that there are always roots of optimal subtrees such that $root[i, j−1]≤root[i,j]≤root[i+1,j] root[i, j - 1]$ for all $1≤i<j≤n$ Use this fact to modify the OPTIMAL-BST$\Theta(n^2)$ time.
## Solution

OPTIMAL-BST
    let e[1...n+1, 0...n], w[1..n+1, 0..n],
        and root[1..n, 1..n] be new tables
    for i = 1 to n +1
        e[i, i-1] = q_(i-1)
        w[i, i-1] = q_(i-1)
    for l = 1 to n
        for i = 1 to n - l + 1  location 6
            j = i + l -1
            e[i, j] = INFINITE
            w[i, j] = w[i, j-1] + p_j + q_j
line 10     for r = i to j 
                t = e[i, r-1] + e[r+1, j] + w[i, j]
                if t < e[i, j]
                    e[i, j] = t
                    root[i, j] = r
    return e and root

The loop at line 10 is meant to find the best root of the subtree.
We can us the prorperty the problem give to change the loop at line 10 to
for $r = r[i, j - 1]$ to $r[i + 1, j]$

First, suppose i = 1, j = 3
then we have the loop
for $r = r[1, 2]$ to $r[2, 3]$
Second, on the next iteration of the loop at location 6
we have i = 2, j = 4 and
for $r = r[2, 3]$ to $r[3, 4]$
Comparing the range of r in the two iteration, we find ==their ranges have nothing to do with n.==

Thus, the time complexity, $O(n^3)$, is redeuced to $O(n^2)$
# Problem 3
[CLRS 3 rd ] Exercise 16.1-3
## Topic
## Solution
1. {(0,10),(8,12),(11,16),(15,18),(17,25)}
always peek the shortest
{(8,12),(15,18)}
but there is a better solution
{(0,10),(11,16),(17,25)}
2. {(0,3),(2,4),(2,4),(3,6),(5,7),(6,8),(7,10),(7,10),(7,10),(9,11),(9,11)}
always peek the one overlaps the fewest
Get: {(0,3),(5,7),(9,11)}

Best: {(0,3),(3,6),(6,8),(9,11)}
3. {(0,10),(6,7),(8,13)}
always peek the earliest
Get: {(0,10)}

Best: {(6,7),(8,13)}

# Problem 4
[CLRS 3 rd ] Exercise 16.1-4
## Topic
## Solution

Scheduling(activities[1..n]){
    calculating the maximal overlap of the activities, 
    which is the minimum of halls we need
    
    suppose the maximal overlap is m
    for i = 1 to n
        for j = 1 to m
            if(the end of the last activity in jth hall 
                is later than the start of ith activity)
                check (j+1)th hall
            else
                put ith activity in jth hall
    return scheduling of 1..nth hall
}

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

bool comp1(tuple<int, int> t1, tuple<int, int> t2){
	return (get<1>(t1) <= get<1>(t2));
}

bool comp2(tuple<int, int> t1, tuple<int, int> t2){
	if(get<0>(t1) < get<0>(t2))
		return 1;
	else if(get<0>(t1) > get<0>(t2))
		return 0;
	else
		return (get<1>(t1) <= get<1>(t2));
}

vector<vector<tuple<int, int>>> scheduling(vector<tuple<int, int>> activities){
	int hall, activity;
	sort(activities.begin(), activities.end(), comp2);
	
	//calculating the maximal overlap
	int overlap = 0;
	for(int i = 1, counter = 1, currentEnd = get<1>(activities[0]), endIndex = 0;i < activities.size();i++){
		if(get<0>(activities[i]) < currentEnd){
			if(overlap < ++counter)
				overlap = counter;
		}
		else{
			while(get<0>(activities[i]) >= get<1>(activities[endIndex])){
				counter--;
				endIndex++;
			}
			currentEnd = get<1>(activities[endIndex]);
		}
	}

	vector<vector<tuple<int, int>>> halls(overlap, vector<tuple<int, int>>(0));
	sort(activities.begin(), activities.end(), comp1);
	for(int i = 0, j, start, end;i < activities.size();i++){
		start = get<0>(activities[i]);
		for(j = 0;j < halls.size();j++){
			if(halls[j].empty()){
				halls[j].push_back(activities[i]);
				break;
			}

			end = get<1>(halls[j][halls[j].size() - 1]);
			if(start < end)
				continue;
			else{
				halls[j].push_back(activities[i]);
				break;
			}
		}
	}
	return halls;
}

int main(){
	vector<tuple<int, int>> activities;
	int start, end, i, j;
	while(cin >> start >> end)
		activities.push_back(make_tuple(start, end));

	vector<vector<tuple<int, int>>> halls = scheduling(activities);
	for(i = 0;i < halls.size();i++){
		cout << "hall" << i + 1 << ": ";
		for(j = 0;j < halls[i].size();j++)
			cout << '(' << get<0>(halls[i][j]) << ", " << get<1>(halls[i][j]) << ")\t";
		cout << endl;
	}
}

# Problem 5
[CLRS 3 rd ] Exercise 16.1-5
(Hint: refer to Exercise 16.1-1)
## Topic
## Solution

Solution(intervals[1..n]){	//intervals[i] = (start::int, end::int, value::int)
	sort intervals by end
	int max[intervals[n].end + 1] // record the maximum in ith moment
	for(i = 0, j = 0;i < n;i++, j++){
		if(i > 0 and intervals[i].end == intervals[i - 1].end)
			j--;
		for(;j < intervals[i].end;j++)
			max[j] = max[j - 1];
		if(intervals[i].value + max[intervals[i].end] > max[j - 1])
			max = intervals[i].value + max[intervals[i].start];
		else
			max = max[j - 1];
	
	return max[intervals[n - 1].end]
}

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

bool comp(tuple<int, int, int> t1, tuple<int, int, int> t2){
	if(get<1>(t1) < get<1>(t2))
		return 1;
	else if(get<1>(t1) > get<1>(t2))
		return 0;
	else{
		if(get<2>(t1) < get<2>(t2))
			return 1;
		else
			return 0;
	}
}

int maximum(vector<tuple<int, int, int>> intervals){
	int i, j;
	sort(intervals.begin(), intervals.end(), comp);
	int max[get<1>(intervals[intervals.size() - 1]) + 1] = {};
	for(i = 0, j = 1;i < intervals.size();i++, j++){
		if(i > 0 && get<1>(intervals[i]) == get<1>(intervals[i - 1]))
				j--;
		for(;j < get<1>(intervals[i]);j++)
			max[j] = max[j - 1];
		max[j] = get<2>(intervals[i]) + max[get<0>(intervals[i])] > max[j - 1] ? get<2>(intervals[i]) + max[get<0>(intervals[i])] : max[j - 1];
	}
	for(i = 0;i < get<1>(intervals[intervals.size() - 1]) + 1;i++)
		cout << max[i] << ' ';
	cout << endl;
	return max[get<1>(intervals[intervals.size() - 1])];
}


int main(){
	int start, end, value;
	vector<tuple<int, int, int>> intervals;
	cout << "input start, end and value, respectively" << endl;
	while(cin >> start >> end >> value)
		intervals.push_back(make_tuple(start, end, value));

	cout << maximum(intervals) << endl;
}

# Problem 6
A variation from [CLRS 3 rd ] Exercise 16.2-2
Given a 0-1 knapsack problem with the knapsack size K and n items, where each
item has its weight in integer and its value in real.
(a) Design an algorithm to find the most valuable load of the items that fit into the
knapsack.
(b) Design a pseudo-polynomial time algorithm to determine the optimal solution that the total weight exactly equals to K.
## Topic
## Solution
### (a)

KNAPSACK(W, set)
    Initialize an (n + 1) by (W + 1) table 
    for i = 0 to n                //0 to ith items
        for j = 0 to W            // current weight limit
            if i==0 ||　ｗ＝０
                table[i][w] = 0;
            else if set[i-1].weight <= w
                 table[i][w] = max(set[i-1].value + 
                                table[i-1][w-set[i-1].weight],  table[i-1][w])
            else
                table[i][w] = table[i-1][w]
                

#include<iostream> 
#include<vector>

using namespace std; 
int max(int a, int b) { return (a > b)? a : b; } 
  struct item{
    int value;
    int weight;
};

void knapSack(int W, vector<item>set) 
{ 
   int i, w, n=set.size(); 
   
   int table[n+1][W+1]; 
  
   for (i = 0; i <= n; i++) //0 to ith items
   { 
       for (w = 0; w <= W; w++) // current weight limit
       { 
           if (i==0 || w==0) 
               table[i][w] = 0; 
           else if (set[i-1].weight <= w) //compare the profits of putting it in or not 
                 table[i][w] = max(set[i-1].value + table[i-1][w-set[i-1].weight],  table[i-1][w]); 
           else//item weight beyond limit
                 table[i][w] = table[i-1][w]; 
       } 
   } 
  
   cout<< table[n][W]<<endl; 

    for (int i = n-1, j = W; i >= 0; --i) //solution
        if (j - set[i].weight >= 0 && table[i+1][j] == table[i][j - set[i].weight] + set[i].value)
        {
            cout <<i<<endl;
            j -= set[i].weight;
        }
} 
  
int main() 
{ 
    int maximum_weight, weight, value;
    vector<item>collection;
    cin>>maximum_weight;
    while(cin>>value>>weight)
        collection.push_back(item{value, weight});
    knapSack(maximum_weight,collection);
    return 0; 
} 

### (b)

KNAPSACK(W, set)

Initialize an (n + 1) by (W + 1) table 
for i = 0 to n                //0 to ith items
    for j = 0 to W            // current weight limit
        if (set[i-1].weight <= w) //compare the profits of putting it in or not 
	    if(w == 0 || i == 0){}
	    else if(set[i - 1].value + table[i - 1][w - set[i - 1].weight].value 
                    > table[i - 1][w].value)
		table[i][w].value = set[i - 1].value 
                                    + table[i - 1][w - set[i - 1].weight].value
		table[i][w].last.value = i - 1
		table[i][w].last.weight = w - set[i - 1].weight
	    else
		table[i][w].value = table[i - 1][w].value
		table[i][w].last.value = table[i - 1][w].last.value
	        table[i][w].last.weight = table[i - 1][w].last.weight
        else if(set[i - 1].weight > w)         //item weight beyond limit
            table[i][w].value = table[i-1][w].value
	    table[i][w].last.value = table[i - 1][w].last.value
	    table[i][w].last.weight = table[i - 1][w].last.weight

                

#include<iostream> 
#include<vector>
#include <stack>

using namespace std; 
int max(int a, int b) { return (a > b)? a : b; } 
  struct item{
    int value = 0;
    int weight = 0;
};

struct item2{
	int value = 0;
	item last;
};

void knapSack(int W, vector<item>set) 
{ 
   int i, w, n=set.size(); 
   
   item2 table[n+1][W+1]; 
  
   for (i = 0; i <= n; i++) //0 to ith items
   { 
       for (w = 0; w <= W; w++) // current weight limit
       { 
           if (set[i-1].weight <= w) //compare the profits of putting it in or not 
			   if(w == 0 || i == 0){}
			   else if(set[i - 1].value + table[i - 1][w - set[i - 1].weight].value > table[i - 1][w].value){
				   table[i][w].value = set[i - 1].value + table[i - 1][w - set[i - 1].weight].value;
				   table[i][w].last.value = i - 1;
				   table[i][w].last.weight = w - set[i - 1].weight;
			   }
		   	   else{
				   table[i][w].value = table[i - 1][w].value;
				   table[i][w].last.value = table[i - 1][w].last.value;
				   table[i][w].last.weight = table[i - 1][w].last.weight;
			   }
           else if(set[i - 1].weight > w){//item weight beyond limit
                 table[i][w].value = table[i-1][w].value;
				 table[i][w].last.value = table[i - 1][w].last.value;
				 table[i][w].last.weight = table[i - 1][w].last.weight;
		   }	
       } 
   } 

   stack<int> index;
   for(i = 0;i <= n;i++){
	   for(w = 0;w <= W;w++)
		   cout << '(' << table[i][w].value << ", " << table[i][w].last.value << ", " << table[i][w].last.weight << ')';
	   cout << endl;
   }

   for(int k = n;k > 0;k--){
	   for(i = table[k][W].last.value, w = table[k][W].last.weight;i > 0 && w > 0;i = table[i][w].last.value, w = table[i][w].last.weight){
	   		index.push(i);
		}
	   if(w == 0){
			index.push(i);
		   	cout << table[k][W].value << endl;
			while(!index.empty()){
				cout << index.top() << ' ';
				index.pop();
			}
			cout << endl;
			return;
	   }
	   else if(i == 0){
             while(!index.empty())
                 index.pop();
             break;
          }
	}
   cout << "No answer" << endl;
}
  
int main() 
{ 
    int maximum_weight, weight, value;
    vector<item>collection;
    cin>>maximum_weight;
    while(cin>>value>>weight)
        collection.push_back(item{value, weight});
    knapSack(maximum_weight,collection);
    return 0; 
}

# Problem 7
[CLRS 3 rd ] Exercise 16.2-6
## Topic
Give a dynamic-programming solution to the 0-1 knapsack problem that runs in **$O(nW)$** time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack.

## Solution
Same as Problem 6(a)

# Problem 8

## Topic
Given a set S of n integers and another integer M, determines whether or not there
exist k elements in S whose sum is exactly M. k is an input parameter.
這題要寫Pseudo Code

Hint:
DP定義: dp[i][j][k]代表從前i個數字取j個數字湊出k, 若可以湊填1, 否則填0
遞迴式: dp[i][j][k] = dp[i-1][j][k] || dp[i-1][j-1][k-S[i]], if k-S[i] >=0
= dp[i-1][j][k], if k-S[i] < 0

## Soluation

#define notFound null
function(Set S, int M, string key = "", int index = 0){
  define static dynamic table DP<string, int>; // storage the other result
  DP[""] = 0;
  forEach((el, i) in S start with index)
    DP[key+str(el)] = DP[key] + el;
    if(DP[key+str(el)]==M)
      return key+str(el);
    if(index<S.length)
      function(S, M, key+str(el)+" ", i+1);
  });
  return notFound;
}
str(any var){
  return stringType(var);
}