The 0/1 Knapsack Problem - Dynamic Programming

 References:
https://www.youtube.com/watch?v=EH6h7WA7sDw

 Class Item

class Item
{
 private $_weight;
 private $_value;
 
 public function __construct($value, $weight)
 {
  $this->_value = $value;
  $this->_weight = $weight;
 }
 
 public function getWeight()
 {
  return $this->_weight;
 }
 
 public function getValue()
 {
  return $this->_value;
 }
}

Fill v array and keep array

$capacity = 5;
$items = array();
$items[] = new Item(0, 0);
$items[] = new Item(5, 3);
$items[] = new Item(3, 2);
$items[] = new Item(4, 1);
//$items[] = new Item(6, 1);

$number_of_items = sizeof($items);
$keep = array();

for($w = 0; $w <= $capacity; $w++) 
{
 $v[0][$w] = 0;
 $keep[0][$w] = 0;
}

for($i = 1; $i < $number_of_items; $i++)
{
 for($w = 0; $w <= $capacity;$w++)
 {
  if($items[$i]->getWeight()<= $w)
  {
   if($v[$i-1][$w] > intval($items[$i]->getValue() + $v[$i-1][$w-$items[$i]->getWeight()]))
   {
    $v[$i][$w] = $v[$i-1][$w];
    $keep[$i][$w] = 0;
   }
   else
   {
    $v[$i][$w] = intval($items[$i]->getValue() + $v[$i-1][$w-$items[$i]->getWeight()]);
    $keep[$i][$w] = 1;
   }
  }
  else
  {
   $v[$i][$w] = $v[$i-1][$w];
   $keep[$i][$w] = 0;
  }
 }
}

Print out the max value of objects will fit in the knapsack

$maxValue = $v[$number_of_items-1][$capacity];
echo 'Max value '. $maxValue . "\n";
$value = 0;
$col = $capacity;
$line = $number_of_items-1;
$k = array();

while($maxValue > $value)
{
 if($keep[$line][$col]==1)
 {
  $value += $items[$line]->getValue();
  $k[] = $items[$line];
  $col = $col - $items[$line]->getWeight();
 }
  $line--;
}

Print out exactly which item:

foreach($k as $key => $value)
{
 echo "Item $key - Value:" . $value->getValue() . " Weight " . $value->getWeight() . "\n";
}

PHP: Custom Array Filter

$my_array = array(2, "a", null, 2.5, NULL, 0, "", 8, -1,array());
 
class ArrayFilter
{
 public static function not_empty($v) 
 {
   if($v !== null && trim($v) !== '' && $v !== array())
   {
  return true;
   }
 }
 
 function filter($values)
 {
  return array_filter($values, "self::not_empty");
 }
}
$arrayFilter = new ArrayFilter();
print_r($arrayFilter->filter($my_array));

Result:

C:\>php -f filter.php
Array
(
    [0] => 2
    [1] => a
    [3] => 2.5
    [5] => 0
    [7] => 8
    [8] => -1
)
C:\>

Một số command khi dùng Git

• Xem log của một file nào đó: git log --follow
• ...


MongoDate và mktime trong PHP

Một vấn đề gặp phải khi sử dụng mktime() để khởi tạo timestamp truyền vào constructor của MongoDate là mktime() sử dụng timezone mặc định trong php.ini trong khi MongoDate lại dùng timestamp theo GMT. Nếu default timezone trong php.ini là Asia/Saigon (GMT+7) thì đối tượng ISODate được khởi tạo trong MongoDB sẽ có thời gian bị lùi về 7h.

Để giải quyết vấn đề này, sử dụng hàm gmmktime() để tạo timestamp theo giờ GMT.

Lưu ý là, hàm date() cũng dùng default timezone mặc định của php.ini. Để có thể chuyển timezone cho hàm date(), dùng hàm date_default_timezone_set(). Ví dụ:

date_default_timezone_set('UTC'); // Set default timezone to GMT

Facebook - Check users' allowed permission for your app

In this entry, we will discover the answer of the question "How to check if the user has already allowed publish_stream for your app?". And luckily, we can achieve this goal by using Grap API. For example I will check whether the user has allowed publish_stream permission or not.

FB.api('/me/permissions', function (response) {
  //please note that we use data[0]
  if(response.data[0].publish_stream==1)
  {
     //Do some stuff such as post a photo to user wall        
  }
  else
  {
    alert('You need to grant "Post on your behalf" permission in order to save to Facebook!');
  }
}

It is easy, isn't it? There is my complete code for force user allow some permission for my app. It is not optimized yet, however it still run OK and meets my need.

FB.getLoginStatus(function(response) {
 if (response.status === 'connected') 
 {
  FB.api('/me/permissions', function (response) {
   if(response.data[0].publish_stream==1)
   {
    FB.api('/me', function(response) {
     
    });
   }
   else
   {
    FB.login(function(response) {
     FB.api('/me/permissions', function (response) {
      if(response.data[0].publish_stream==1)
      {
       //Do some stuff that need permissions
      }
      else
      {
       alert('You need to grant "Post on your behalf" permission in order to save to Facebook!');
      }
     });
    },
                                  {scope:'publish_stream,user_photos,user_birthday,email'});
   }
  });
 }
 else if (response.status === 'not_authorized')
 {
  FB.login(function(response) {
   if (response.authResponse) 
   {
    FB.api('/me/permissions', function (response) {
      if(response.data[0].publish_stream==1)
      {
      
      }
      else
      {
        alert('You need to grant "Post on your behalf" permission in order to save to Facebook!');
      }
    });
   } 
   else 
   {
    alert('You need to authorize the application before you do other action');
   } 
  }, {
   scope : 'publish_stream,user_photos,user_birthday,email'
  });
 }
});

Hung Nguyen

Replace 4 spaces to tabs

Hôm nay dùng SVN mới biết là mặc định NetBeans dùng 4 spaces thay vì 1 tab khi chọn chuột phải format, làm update code từ SVN về đỏ lòm, mặc dù cũng không có conflict gì. Giải pháp là bỏ chọn "Expand Tabs to Spaces" trong Options của NetBeans để sau này format thì NB sẽ dùng tab thay vì spaces. Nhớ giảm Tab size còn lại 4 spaces thôi ^^.

Rồi sau đó việc còn lại là Find and Repalce 4 spaces thành 1 tab cho toàn bộ project ^^". May mắn là có chứng năng Find in Files của Notepad++, chỉ cần replace 4 spaces thành "\t" là ok.

(*) with Search Mode Extended

Default unicode encoding for notepad document

This tip just applies for context menu (Right Click->New->Text Document)

1. Create a new .txt document and do not type anything
2.  Named the file above "txtunicode.txt." and save to C:\Windows\ShellNew\ (with unicode encoding)
3. Then go to run dialog type "regedit" to open Registry Editor
4. Navigate to HKEY_CLASSES_ROOT\.txt\ShellNew
5. Right click to right windows select New->String value and rename to FileName
6. Then type "txtunicode.txt" and click OK - it's finished

Now you can test be create new text document in context menu