-----------------------------------

riveryu

Thu Jun 12, 2008 10:38 pm


A bit too wise for me....

-----------------------------------

Can someone explain the tetris problem that used this concept?


var files : array 1 .. 10 of int := init (24, 235, 41, 21, 353, 61, 431, 927, 81, 46) 
var N : int := 700 
var best : int := 0 

for i : 0 .. 2 ** upper (files) - 1 %loop through every combination 
    var temp : int := 0  %stores the sum of the files in current combination 
    for j : 1 .. upper (files)  %loops through each bit 
        if (i & (1 shl (j - 1))) > 0 then  %checks the bit if it is high 
            temp += files (j)  %adds the file to the sum 
        end if 
    end for 
    if temp  best then  %checks whether the current combination is better then the current best 
        best := temp 
    end if 
end for 



-----------------------------------

DemonWasp

Fri Jun 13, 2008 6:50 am


RE:A bit too wise for me....

-----------------------------------

It looks like it may be trying to decide which is the best combination of files to write to a CD to maximise space usage. Note that they have N = 700 (MB on a CD?), files[] (sizes in MB?) and they "loop through every combination", checking each one to see if it's both less than N and better than their previous best.

The usage of the for loop here is obfuscated, but it's essentially just iterating over all possible combinations. If you know bitwise stuff, you should be able to puzzle that out.

I'm fairly certain this isn't even related to a tetris game implementation.