;============================================================
;  アルゴリズム 31〜35: 動的計画法 (DP)
;    31. 0/1 Knapsack
;    32. Unbounded Knapsack
;    33. Longest Increasing Subsequence (LIS) O(N log N)
;    34. Coin Change (最小枚数)
;    35. Edit Distance (operations trace 付)
;============================================================

#include "hsp3cl_net_64.as"

; ----- 31. 0/1 Knapsack -----
#module
#defcfunc knapsack_01 array _w, array _v, int _n, int _cap, \
	local _i, local _j, local _alt
	dim _dp, (_n + 1) * (_cap + 1)
	repeat _n
		_i = cnt + 1
		repeat _cap + 1
			_j = cnt
			_dp(_i * (_cap + 1) + _j) = _dp((_i - 1) * (_cap + 1) + _j)
			if _j >= _w(_i - 1) {
				_alt = _dp((_i - 1) * (_cap + 1) + _j - _w(_i - 1)) + _v(_i - 1)
				if _alt > _dp(_i * (_cap + 1) + _j) : _dp(_i * (_cap + 1) + _j) = _alt
			}
		loop
	loop
	return _dp(_n * (_cap + 1) + _cap)
#global

; ----- 32. Unbounded Knapsack -----
#module
#defcfunc knapsack_un array _w, array _v, int _n, int _cap, \
	local _i, local _j, local _alt
	dim _dp, _cap + 1
	repeat _cap
		_j = cnt + 1
		repeat _n
			_i = cnt
			if _w(_i) <= _j {
				_alt = _dp(_j - _w(_i)) + _v(_i)
				if _alt > _dp(_j) : _dp(_j) = _alt
			}
		loop
	loop
	return _dp(_cap)
#global

; ----- 33. LIS (O(N log N), patience) -----
#module
#defcfunc lis array _a, int _n, \
	local _i, local _lo, local _hi, local _mid, local _len
	dim _tails, _n
	_len = 0
	repeat _n
		_i = cnt
		_lo = 0 : _hi = _len
		repeat
			if _lo >= _hi : break
			_mid = (_lo + _hi) / 2
			if _tails(_mid) < _a(_i) : _lo = _mid + 1 : else : _hi = _mid
		loop
		_tails(_lo) = _a(_i)
		if _lo == _len : _len++
	loop
	return _len
#global

; ----- 34. Coin Change (最小枚数) -----
#module
#defcfunc coin_change array _coins, int _m, int _amt, \
	local _i, local _j, local _INF, local _alt
	_INF = 0x7FFFFFFF
	dim _dp, _amt + 1
	repeat _amt : _dp(cnt + 1) = _INF : loop
	repeat _amt
		_i = cnt + 1
		repeat _m
			_j = cnt
			if _coins(_j) <= _i : if _dp(_i - _coins(_j)) != _INF {
				_alt = _dp(_i - _coins(_j)) + 1
				if _alt < _dp(_i) : _dp(_i) = _alt
			}
		loop
	loop
	if _dp(_amt) == _INF : return -1
	return _dp(_amt)
#global

; ----- 35. Edit Distance + Trace -----
#module
#deffunc edit_distance_trace var _a, var _b, var _dst, var _ops, \
	local _i, local _j, local _la, local _lb, local _a1, local _a2, local _a3, local _m, \
	local _ci, local _cj
	_la = strlen(_a) : _lb = strlen(_b)
	dim _dp, (_la + 1) * (_lb + 1)
	repeat _la + 1 : _dp(cnt * (_lb + 1)) = cnt : loop
	repeat _lb + 1 : _dp(cnt) = cnt : loop
	repeat _la
		_i = cnt + 1
		repeat _lb
			_j = cnt + 1
			_ci = peek(_a, _i - 1)
			_cj = peek(_b, _j - 1)
			if _ci == _cj {
				_dp(_i * (_lb + 1) + _j) = _dp((_i - 1) * (_lb + 1) + _j - 1)
			} else {
				_a1 = _dp((_i - 1) * (_lb + 1) + _j) + 1
				_a2 = _dp(_i * (_lb + 1) + _j - 1) + 1
				_a3 = _dp((_i - 1) * (_lb + 1) + _j - 1) + 1
				_m = _a1
				if _a2 < _m : _m = _a2
				if _a3 < _m : _m = _a3
				_dp(_i * (_lb + 1) + _j) = _m
			}
		loop
	loop
	_dst = _dp(_la * (_lb + 1) + _lb)
	sdim _ops, 512
	_ops = ""
	_i = _la : _j = _lb
	repeat
		if (_i <= 0) & (_j <= 0) : break
		if (_i > 0) & (_j > 0) {
			_ci = peek(_a, _i - 1) : _cj = peek(_b, _j - 1)
			if _ci == _cj : _i-- : _j-- : continue
			if _dp(_i * (_lb + 1) + _j) == _dp((_i - 1) * (_lb + 1) + _j - 1) + 1 {
				_ops = strf("replace '%c'->'%c' at %d\n", _ci, _cj, _i - 1) + _ops
				_i-- : _j-- : continue
			}
		}
		if _i > 0 : if _dp(_i * (_lb + 1) + _j) == _dp((_i - 1) * (_lb + 1) + _j) + 1 {
			_ci = peek(_a, _i - 1)
			_ops = strf("delete '%c' at %d\n", _ci, _i - 1) + _ops
			_i--
			continue
		}
		_cj = peek(_b, _j - 1)
		_ops = strf("insert '%c' at %d\n", _cj, _i) + _ops
		_j--
	loop
	return
#global

; ===== デモ =====
	mes "=== 0/1 Knapsack ==="
	dim kw, 3 : kw = 2, 3, 4
	dim kv, 3 : kv = 3, 4, 5
	v01 = knapsack_01(kw, kv, 3, 5)
	mes strf("items=(w:2,v:3),(w:3,v:4),(w:4,v:5), cap=5  => max=%d", v01)
	mes strf("Unbounded: max=%d", knapsack_un(kw, kv, 3, 5))

	mes ""
	mes "=== LIS ==="
	dim la_arr, 8 : la_arr = 10, 22, 9, 33, 21, 50, 41, 60
	mes strf("LIS of [10,22,9,33,21,50,41,60] = %d (期待: 5)", lis(la_arr, 8))

	mes ""
	mes "=== Coin Change ==="
	dim c, 3 : c = 1, 3, 4
	mes strf("min coins for 6 (from {1,3,4}) = %d",  coin_change(c, 3, 6))
	mes strf("min coins for 11 = %d",                coin_change(c, 3, 11))

	mes ""
	mes "=== Edit Distance with trace ==="
	s1 = "kitten" : s2 = "sitting"
	edit_distance_trace s1, s2, dst, ops
	mes strf("Distance = %d", dst)
	mes "Operations:"
	mes ops
	end 0