#!/usr/bin/perl -w
# 演算法: knapsack problem 背包問題, 兩個版本.
# 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung
# 授權: public domain (但如果您要將我的程式改寫成有用的大程式,
#	強烈建議將您的版本施以 GPL)

# 使用方式: 把 $store = ... 修改成你的物品資料, 格式為:
#	{ n=>"物品名稱", v=>價值, w=>重量, c=>可取用個數 },
# 並修改負重限制. 物品名稱可以是任何合法的變數名稱.
# (但若超過兩個字母, 印出來會有點醜) 最後下
#	perl knapsack
# 命令執行程式.
# 印出來的結果, 前半部是 "同種物品無限量供應版本"; 後半部是
# "同種物品指定限量供應版本" .
# 提示: 試試看將 "每單位重量最有價值" 的物品供應量減少, 更容易了解
# 兩演算法的差異.

use strict;

sub ks_ul {	# 同種物品無限量供應版本
    my ($limit, $store) = @_;
    my (
	# 以下是迴圈的最主要註標變數:
	$item,		# 正在處理的物件 $item
	$load,		# 正在處理的負重限制 $load
	# 以下是動態規劃中的主要表格:
	$value,		# $value->[$i] 記載負重 $i 限制下的最高價值.
	$last,		# $last->[$i]  記載負重限制 $i 下的最佳解,
			# 所應取的物品當中, 最後取的那一件是何種物品?
    );

    my ($tics) = "   ";
    map { $tics .= $_ % 5 == 0 ? sprintf "-%2d", $_ : "---"; } 1..$limit;
    print "$tics\n";
    @$value = (0) x ($limit+1);
    for ($item=0; $item<=$#$store; ++$item) {
	my ($out);	# 即將印出來的字串, 暫存於此
	my ($t) = $store->[$item];
	for ($load=1; $load<=$limit; ++$load) {
	    if ($load >= $t->{w} and
		$value->[$load] < $value->[$load-$t->{w}] + $t->{v}) {
		$value->[$load] = $value->[$load-$t->{w}] + $t->{v};
		$last->[$load] = $item;
	    }
	    $out->[0] .= sprintf "%3d", $value->[$load];
	    $out->[1] .= sprintf " %2s", defined $last->[$load] ?
		$store->[$last->[$load]]->{n} : "-";
	}
	printf "%2s:$out->[0]\n   $out->[1]\n", $t->{n};
    }
    print "$tics\n";
    $load = $limit;
    my ($out);
    while ($load > 0) {
	my ($t) = $store->[$last->[$load]];
	$out->[0] .= sprintf "%3s", $t->{n};
	$out->[1] .= sprintf "%3d", $t->{v};
	$out->[2] .= sprintf "%3d", $t->{w};
	$load -= $t->{w};
    }
    printf "     $out->[0]\n%3d |$out->[1]\n%3d |$out->[2]\n\n",
	$value->[$limit], $limit;
}

sub ks_count {		# 同種物品指定限量供應版本
    my ($limit, $store) = @_;
    my (
	# 以下是迴圈的最主要註標變數:
	$load,		# 正在處理的負重限制 $load
	$item,		# 正在處理的物件 $item
	# 以下是動態規劃中的主要表格:
	$value,		# $value->[$i] 記載負重限制 $i 下的最高價值.
	$last,		# $last->[$i]  記載負重限制 $i 下的最佳解,
			# 所應取的物品當中, 最後取的那一件是何種物品?
    );

    unshift @$store, { n=>"-", v=>0, w=>1, c=>9999 };
    print "val/lim | bi";
    for ($item=1; $item<=$#$store; ++$item) {
	printf " %2s", $store->[$item]{n};
    }
    $value->[0] = 0;
    for ($load=1; $load<=$limit; ++$load) {
	my ($best_item, $best_val) = (0, 0);
	for ($item=1; $item<=$#$store; ++$item) {
	    my ($i) = $store->[$item];
	    my ($ll) = $load - $i->{w};	# lighter load
	    # 是否可捨棄一些東西, 騰出重量改拿 $item ...
	    next if ($ll < 0);
	    # 價值會更高嗎?
	    my ($new_val) = $value->[$ll] + $i->{v};
	    next if $new_val <= $best_val;
	    # 還有得拿嗎?
	    next if taken($ll, $item, $last, $store) >= $i->{c};
	    $best_item = $item;
	    $best_val = $new_val;
	}
	$value->[$load] = $best_val;
	$last->[$load] = $best_item;
	printf "\n%3d/%3d | %2s", $best_val, $load, $store->[$best_item]{n};
	for ($item=1; $item<=$#$store; ++$item) {
	    printf "%3d", taken($load, $item, $last, $store);
	}
    }
    print "\n";
}

sub taken {		# 負重限制 $load 下的最佳解, $item 類物品取了幾件?
    my ($load, $item, $last, $store) = @_;
    my ($n) = 0;
    while ($load > 0) {
	my ($t) = $store->[$last->[$load]];
	++$n if $t->{n} eq $store->[$item]{n};
	$load -= $t->{w};
    }
    return $n;
}

my ($store);

$store = [
    {n=>"A", v=>19, w=>  5, c=> 6},
    {n=>"B", v=>24, w=>  6, c=> 6},
    {n=>"C", v=>33, w=>  8, c=> 5},
    {n=>"D", v=>45, w=> 11, c=> 1},
    {n=>"E", v=>50, w=> 12, c=> 1},
];
# $store = [
#     {n=>"a", v=>10, w=> 3, c=> 3},
#     {n=>"b", v=>13, w=> 4, c=> 9},
#     {n=>"c", v=>17, w=> 5, c=> 3},
#     {n=>"d", v=>25, w=> 7, c=> 1},
#     {n=>"e", v=>32, w=> 9, c=> 1},
# ];
# $store = [
#     {n=>"A", v=> 4, w=> 3, c=> 2},
#     {n=>"B", v=> 5, w=> 4, c=> 3},
#     {n=>"C", v=>10, w=> 7, c=> 2},
#     {n=>"D", v=>11, w=> 8, c=> 5},
#     {n=>"E", v=>13, w=> 9, c=> 2},
#     {n=>"F", v=>15, w=>10, c=> 1},
# ];

my ($i);
print " name : "; foreach $i (@$store) { printf "%3s", $i->{n}; } print "\n";
print " value: "; foreach $i (@$store) { printf "%3d", $i->{v}; } print "\n";
print " wght : "; foreach $i (@$store) { printf "%3d", $i->{w}; } print "\n";
print "(count: "; foreach $i (@$store) { printf "%3d", $i->{c}; } print ")\n";
print "\n";
ks_ul(25, $store);
ks_count(45, $store);