Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Knapsack problem
#1
How can I do this in QM?

Given a sequence of positive integers, and another integer (goal)
find a subset of the items such that their sum is less or equal to
the goal, but as large as possible.


-- Possible uses:
-- Fill CD's, DVD's, diskettes to the brim.
-- Combine cheques to pay exact amount.
-- Equitably divide goods (for example between heirs).
-- Etc.
#2
Windows does not provide math functions. msvcrt.dll provides only simple functions such as sqrt. Google for an algorithm or code sample or COM/dll component.
#3
I found http://www.uic.nnov.ru/~zny/knapsack/hs.c

Can you help me to convert it to function QM?
#4
Better compile it to dll. It easier than convert to QM. In QM it would be slow.
#5
and:

procedure show(sequence cost, sequence mat, integer j)
integer c, len
sequence temp
len = length(cost)
printf(1, "%d=", j - 1)
while j > 1 do
temp = mat[j]
for i = 1 to len do
if temp[i] then
c = cost[i]
printf(1,"+%d", c)
j -= c
exit
end if
end for
end while
puts(1, "\n")
end procedure

procedure showall(sequence cost, sequence mat, integer j)
integer c, len, k, i, m, f, h
sequence temp, v
len = length(cost)
v = repeat(0, j)
v[j] = len + 1
k = j
i = 1
while 1 do
temp = mat[k]
f = 1
while i < v[k] do
if temp[i] then
k -= cost[i]
v[k] = i
if k = 1 then
printf(1, "%d=", j - 1)
m = 1
h = i
while m < j do
c = cost[h]
printf(1, "+%d", c)
m += c
h = v[m]
end while
puts(1, "\n")
exit
end if
f = 0
i = 1
exit
end if
i += 1
end while
if i > len then
exit
end if
if f then
k += cost[i]
i += 1
end if
end while
puts(1, "\n")
end procedure

procedure knapsack(sequence cost)
sequence sol, mat
integer tot, len, c, v
object ct
len = length(cost)
-- Check data and compute maximum possible goal value
-- (plus 1 because the EU index origin is 1)
tot = 1
for i = 1 to len do
ct = cost[i]
if integer(ct) and ct > 0 then
tot += ct
else
puts(1, "Only positive integers allowed")
exit
end if
end for
sol = repeat(0, tot)
mat = repeat(repeat(0, len), tot)
-- mat[x][y]=1 means that total x-1 may contain cost[y]
for i = 1 to len do
c = cost[i]
for j = tot to 1 by -1 do -- down to avoid spurious repetitions
if sol[j] then
v = j + c
if v <= tot then
sol[v] = 1
mat[v][i] = 1
end if
end if
end for
sol[c + 1] = 1
mat[c + 1][i] = 1
end for
for j = 1 to tot do
if sol[j] then -- only for sum strictly equal to the goal
show(cost, mat, j)
end if
end for
puts(1, "\n")
end procedure

-- Sample data.

knapsack({2, 3, 5, 7, 10})

knapsack({343,785,351,221,248,177,143,217,154,166,235,96,362,177,232,146,351,290,346,178,191})
#6
Don't know this language.
#7
How can I compile http://www.uic.nnov.ru/~zny/knapsack/hs.c to dll?
#8
To compile C++ code you need a program that does it. There are many free C++ compilers and IDEs (integrated development environment).

http://www.thefreecountry.com/compilers/cpp.shtml

I tested only few, in the past:

Microsoft Visual C++ 2005/2008 Express. Don't have a resource editor, but you don't need it in this case.

Bloodshed Dev-C++.

---

Download the program. Install.

Run the program.

Create new Win32 dll project. It should create minimum code for the dll. The code should contain DllMain function.

Try to compile (Build) to see if the compiler works well. Must compile without errors. It will create a dll file somewhere in project's folder.

Below or above WinMain function, add your functions. Don't add main() function.

Before each function you want to export (and use in QM) insert extern "C" __declspec(dllexport). With non-Microsoft compilers it may not work. Then can be used def file.

Compile. Must compile without errors. If not, then you have to learn C++ and correct the code.

In QM, declare the exported functions, for example

Code:
Copy      Help
dll "$desktop$\knaps\release\knaps.dll" knapsack_hs n int*w c int*p int*z int*x

Ready to use.
#9
Just installed Microsoft Visual C++ 2008 Express Beta 2. Compiles the code without errors.

Some settings should be changed. On the toolbar, select Release instead of Debug. Also select 'project properties -> configuration properties -> C/C++ -> code generation -> runtime library -> multi threaded'.

With 2005 version everything is the same.
#10
I tried to translate the 2º algorithm to QM but fails.

Can you help me to find the error?

The language is http://www.rapideuphoria.com/


Attached Files
.qml   knapsack.qml (Size: 1.02 KB / Downloads: 459)
#11
Gintaras Wrote:Better compile it to dll. It easier than convert to QM. In QM it would be slow.

Could be done now with the version 2.3.2?
#12
Probably yes. Try the __Tcc sample macros and then try to create dll from the c file.
#13
Macro knapsack
Code:
Copy      Help
;Before:
;Edit the downloaded hs.c file:
;;;;Before each function that you'll need, insert this line: __declspec(dllexport)
;;;;These functions are knapsack_sort knapsack_hs knapsack_restore.

;Then run this macro. It creates dll on desktop.

UnloadDll("$desktop$\knapsack.dll")
__Tcc x.Compile(":D:\Downloads\hs.c" "$desktop$\knapsack.dll" 2)

;Then you can use the dll.
;Function declarations:
dll- "$desktop$\knapsack.dll"
,#knapsack_hs n *w c *p *z *x
,#knapsack_sort *a *b n *perm
,#knapsack_restore *x n *perm

;Or you can create code in memory instead of creating dll.
#14
Thanks.

Do you know how to combine the algorithm and "enumerate files" to get the optimal files to burn to a cd/dvd?
#15
At first I have to know how to use these knapsack functions. Do you have an example code without enumerating files?
#16
Sorry, no.
#17
I don't know how to use these functions. What are the arguments.


Forum Jump:


Users browsing this thread: 1 Guest(s)