473,836 Members | 1,903 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

0-1 Knapsack Problem and the Greedy Algorithm

4 New Member
Ok, so, for those of you that are unfamiliar with the 0-1 Knapsack problem, I have to write an to take the weights and corresponding values of 10 items, and find which items to put in a knapsack that holds 85 pounds to have the maximum value in the knapsack.

I keep getting compiler errors, and quite honestly, I'm really bad at debugging.

Code:
Expand|Select|Wrap|Line Numbers
  1. // The "Knapsack" class.
  2. public class Knapsack
  3. {
  4.     public static void main (String[] args)
  5.     {   int n;
  6.     int nmax = 10;
  7.     int wmax = 85;
  8.     int w;
  9.     int addVal;  
  10.     int itemArray = new int [2][nmax];
  11.  
  12.     int solArray = new int [nmax][wmax];
  13.  
  14.     itemArray = {{10, 63, 84, 81, 33, 11, 67, 10, 65, 81}, { 9, 19, 5, 31, 48, 17, 46, 80, 38, 55}};
  15.  
  16.  
  17.     //This section of code fills the first row of the Solution Array
  18.     while(w <= wmax){
  19.  
  20.         if (itemArray [0][0] < w){
  21.         solArray[0][w] = itemArray[0][1];
  22.         }
  23.  
  24.         else solArray[0][w] = 0;
  25.  
  26.     }
  27.  
  28.  
  29.  
  30.      for (n = 1; n <= nmax-1; n++){
  31.  
  32.         for(w = 1; w <= wmax-1; w++){
  33.  
  34.             //checks to see if the item being looked at weighs more than the subproblem can carry
  35.             if (itemArray[0][n] > w){
  36.                 solArray[n][w] = solArray[n-1][w];
  37.             }
  38.  
  39.             //adds together the values of the previous subproblem and the current iteration of n
  40.             //and checks if it is of greater value than the previous row
  41.             addVal = solArray[n-1][w-itemArray[0][n]] + itemArray[1][n];
  42.             if (addVal > solArray[n-1][w]){
  43.             solArray[n][w] = addVal;
  44.             }
  45.  
  46.             //if only the current item can be fit in the knapsack, checks if the item is more valuable than the value in the row above              
  47.             else if (w >= itemArray[0][n] && solArray[n-1][w] < itemArray[1][n])
  48.             {solArray[n][w] = itemArray[1][n];}
  49.  
  50.             else solArray[n][w] = solArray[n-1][w];
  51.  
  52.  
  53.         }       
  54.     }
  55.  
  56.  
  57.     n = nmax-1;
  58.     w = wmax-1;
  59.     int includeArray = new int[i];
  60.     int i = 0;
  61.  
  62.     //populates a 1-dimensional array with the numbers of the items filling the knapsack in the optimal solution
  63.     while (n <= 0){
  64.         if ((solArray[n][w] != solArray[n-1][w]) && (solArray [n-1][w] != 0)){
  65.             includeArray[i] = n;
  66.             w = w - itemArray[0][n];
  67.             i++;
  68.         }
  69.  
  70.             n--;
  71.     }       
  72.  
  73.     includeArray.length = i;
  74.  
  75.     //print out solution array
  76.     for (n = 0; n <= nmax; n++){
  77.         for (w = 0; w <=wmax; w++){
  78.             System.out.println(solArray[n][w]);
  79.         }
  80.     }
  81.  
  82.     } // main method
  83. } // Knapsack class
P.S. NOOOOO, the forum messes with all my nice indentation!
Mar 7 '08 #1
8 22272
BigDaddyLH
1,216 Recognized Expert Top Contributor
Please enclose your posted code in [code] tags (See How to Ask a Question).

This makes it easier for our Experts to read and understand it. Failing to do so creates extra work for the moderators, thus wasting resources, otherwise available to answer the members' questions.

Please use [code] tags in future.

MODERATOR
Mar 7 '08 #2
Tehcuod
4 New Member
Please enclose your posted code in [code] tags (See How to Ask a Question).

This makes it easier for our Experts to read and understand it. Failing to do so creates extra work for the moderators, thus wasting resources, otherwise available to answer the members' questions.

Please use [code] tags in future.

MODERATOR
Heh, thanks! I apparently need to learn to read.
Mar 7 '08 #3
BigDaddyLH
1,216 Recognized Expert Top Contributor
Well, knowing syntax is a prerequisite for programming. It's not debugging. Anyhowdy, I'll get you started: the syntax used to assign to an array variable can only be used to initialize an array:
Expand|Select|Wrap|Line Numbers
  1. int[][] itemArray = {{10, 63, 84, 81, 33, 11, 67, 10, 65, 81}, { 9, 19, 5, 31, 48, 17, 46, 80, 38, 55}};
  2.  
Mar 7 '08 #4
Tehcuod
4 New Member
Ah, thanks, I'm kinda rusty on my arrays, and Java in general... and for some reason I couldn't figure out the syntax for that.
Mar 7 '08 #5
BigDaddyLH
1,216 Recognized Expert Top Contributor
Ah, thanks, I'm kinda rusty on my arrays, and Java in general... and for some reason I couldn't figure out the syntax for that.
I left a few syntax errors for you to fix ;-)
Mar 7 '08 #6
Tehcuod
4 New Member
I left a few syntax errors for you to fix ;-)
Ok, well, one thing I've been having issues with that I'm sure isn't right is with my includeArray[]

How does one go about handling an array that they don't know the length of until the while loop below has been iterated through?
Mar 7 '08 #7
BigDaddyLH
1,216 Recognized Expert Top Contributor
Ok, well, one thing I've been having issues with that I'm sure isn't right is with my includeArray[]

How does one go about handling an array that they don't know the length of until the while loop below has been iterated through?
The best way is not to use arrays at all. I seldom use arrays, apart from trivial uses. Use an appropriate collection class:

http://java.sun.com/docs/books/tutor...ons/index.html
Mar 7 '08 #8
DANILIN
24 New Member
Knapsack 0-1 & rosettacode & qbasic qb64 & WE

Classic Knapsack problem is solved in many ways

Contents: http://rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_proble m/0-1

My newest program synthesizes all ciphers from 0 & 1
adding an extra register and 0 remain on left in cipher

Number of comparisons decreases from N! to 2^N
for example N=5 N!=120 >> 2^N=32

Random values origin are automatically assigned
quantity and quality and integral of value is obtained
and in general: integral of quantity and quality
and it is possible to divide only anyone will not understand

Program write results to qb64 directory

Expand|Select|Wrap|Line Numbers
  1. Open "knapsack.txt" For Output As #1
  2. N=7: L=5: a = 2^(N+1): Randomize Timer 'knapsack.bas DANILIN
  3. Dim L(N), C(N), j(N), q(a), q$(a), d(a)
  4.  
  5. For m=a-1 To (a-1)/2 Step -1: g=m: Do ' sintez shifr
  6.     q$(m)=LTrim$(Str$(g Mod 2))+q$(m)
  7.     g=g\2: Loop Until g=0
  8.     q$(m)=Mid$(q$(m), 2, Len(q$(m))) 
  9. Next
  10.  
  11. For i=1 To N: L(i)=Int(Rnd*3+1) ' lenght & cost
  12. C(i)=10+Int(Rnd*9): Print #1, i, L(i), C(i): Next ' origin
  13.  
  14. For h=a-1 To (a-1)/2 Step -1
  15.     For k=1 To N: j(k)=Val(Mid$(q$(h), k, 1)) ' from shifr
  16.         q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
  17.         d(h)=d(h)+L(k)*j(k)
  18.     Next
  19.     If d(h) <= L Then Print #1, d(h), q(h), q$(h)
  20. Next
  21. max=0: m=1: For i=1 To a
  22.     If d(i)<=L Then If q(i) > max Then max=q(i): m=i
  23. Next
  24. Print #1,: Print #1, d(m), q(m), q$(m): End
Main thing is very brief and clear to even all

Results is reduced manually:

Expand|Select|Wrap|Line Numbers
  1.  1             2             17 
  2.  2             2             14 
  3.  3             2             17 
  4.  4             1             11 
  5.  5             2             18 
  6.  6             3             14 
  7.  7             3             10 
  8.  
  9.  5             73           1101000
  10.  2             28           0100000
  11.  5             81           0011100 !!!
  12.  3             45           0011000
  13.  5             76           0010010
  14.  2             36           0000100
  15.  
  16.  5             81           0011100
May 22 '22 #9

Sign in to post your reply or Sign up for a free account.

Similar topics

6
8892
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit time to complete. Suppose further that each task has a deadline by which it is expected to finish. IF a task is not finished by the deadline, a standard penalty of $10 is applied. The problem is to find a schedule of the tasks that minimizes the...
12
4441
by: lothar | last post by:
re: 4.2.1 Regular Expression Syntax http://docs.python.org/lib/re-syntax.html *?, +?, ?? Adding "?" after the qualifier makes it perform the match in non-greedy or minimal fashion; as few characters as possible will be matched. the regular expression module fails to perform non-greedy matches as described in the documentation: more than "as few characters as possible"
5
4219
by: Koen | last post by:
Hi, I am looking for an algorithm that figures out which numbers from a given set add up to another number. I am sure this has been done before, but I have no idea how such a calculation is called, which kind of limits my further searching. An example. The set contains the numbers 1-2-3-4-5. Now the algorithm should calculate all possible combinations of these numbers that add up to 10. Each number can be used more than one time or...
3
1592
by: Frank | last post by:
Hi all, I have a programming problem and am not sure what's the best way to come to a solution. Problem: I want to know how many blocks fit into a box. The blocks are all the same size, but are not cubes. So you can put them upstraight or lay down. Or start a layer upstraight and then a layer layed down. Any number of possibilities.
8
2476
by: John Hazen | last post by:
I want to match one or two instances of a pattern in a string. According to the docs for the 're' module ( http://python.org/doc/current/lib/re-syntax.html ) the '?' qualifier is greedy by default, and adding a '?' after a qualifier makes it non-greedy. > The "*", "+", and "?" qualifiers are all greedy... > Adding "?" after the qualifier makes it perform the match in > non-greedy or minimal fashion...
6
2729
by: EXI-Andrews, Jack | last post by:
the '*' and '+' don't seem to be greedy.. they will consume less in order to match a string: ('aa', 'ab') this is the sort of behaviour i'd expect from '(a+?)(ab)' a+ should greedily consume a's at the expense of the string not matching
3
4514
by: Van Dugall | last post by:
I writing a economic statistics program.. I need to allocate billions of dollars and I have been shown projects to consider and ith project estimates its cost to be dollars and claims to generate jobs. So I have B billions of dollars n projects ci dollars Ji jobs
3
8519
by: amriksingh24 | last post by:
i have to write a function that given a graph G,produces a greedy colouring of vertices using welsh - powell algorithm
0
1445
by: awasthiastha | last post by:
what is the code for greedy algorithm in c++ for routing algorithms in networking?
0
9654
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10526
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10565
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9348
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
6972
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5809
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4436
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
3999
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3094
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.