 # Programming trouble (code in c++).Help needed !

This is a project for school.
We’ve been asked to make the following program with c++ .

However I’ve got aproblem I need to solve.
Here is the program :
Let’s suppose we need to build a wall with a certain amount of some bricks. My task is to choose the appropriate bricks from the ones given to me to make the wall. The total surface of the wall should be as closer to the desired as possible.

The program should actually read 1 input file which has the following data:

The first line has 2 numbers :
The total size of the wall should be a number between 100 and 10000 (100<= s1 <10000).
The total number of bricks that can be used which is a number between 10 and 1000
(10<= n <1000)

The next n lines contain the surface of each brick which can be a number between
1 and 900 (1< E <= 900)

Then the program should create an output file like the one described below:
In the first line of the output file the first line should contain the number of the bricks used to make the wall which should be a number between 2 and 1000 (2<=k<1000).
The next k lines should contain the numbers of the bricks used with declining order

Here are the two test cases I am testing:

Input file 1
100 10
40
22
11
20
7
8
6
2
3
4

Output file 1
5
1
2
4
3
5

Input file 2
100 10
40
22
11
20
9
8
6
2
3
4

Output file 2
6
1
2
4
3
10
9

Here is what have I done until now in C++ (Right now my program does not reads or writes files as I still test it so I pass the data manually into the code and print results to the screen.) :

#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;

struct brick
{
int size;
int pos;
};

int s1 = 100;
int n=10;
brick inp,tmp;
int b,c,j,ri,e;

int main(int argc, char* argv[])
{
// start of initialization
inp.size = 40; inp.pos=1;
inp.size = 22; inp.pos=2;
inp.size = 11; inp.pos=3;
inp.size = 20; inp.pos=4;
inp.size = 9; inp.pos=5;
inp.size = 8; inp.pos=6;
inp.size = 6; inp.pos=7;
inp.size = 2; inp.pos=8;
inp.size = 3; inp.pos=9;
inp.size = 4; inp.pos=10;
//end of initialization

//let’s add some buble sort(we need to sort them before starting)…
for(b=0;b<=n-1;b++)
{
for (c=n-1;c>=b;c–)
{
if (inp[c+1].size > inp[c].size)
{
tmp=inp[c+1];
inp[c+1]=inp[c];
inp[c]=tmp;
}
}
}

for (b=0;b<=n-1;b++)
{
cout << inp.size << "
";
}
cout << "
";
//end of bubble sort

//here we start
j=0;
ri=0;

//starts counting
while (j<=n-1 && s1>=0)
{
if ( s1>=inp[j].size)
{
cout << inp[j].pos <<"
";
s1=s1-inp[j].size;
j++;
ri++;
}
else
{
j++;
}
}

//starts output
cout << "
" << "
" << ri;
cin >> e;

return 0;
}

My problem is that although my program works fine with the first test case ,it produces a false output with the second one.

Here is the false output:

5
1
2
4
3
7

How can I fix this ?

I thought I knew but now Im not sure

I’ll take a look at it. You would have an easier time if you just used the I/O of C++:

``````cin &gt;&gt; total_area_of_wall;
cin &gt;&gt; total_number_of_bricks;

cout &lt;&lt; number_of_bricks_used;
...
``````

Then you could test it at the command line

``````bricks.exe &lt; test_file_1.txt &gt; output_file_1.txt
``````

I still have to examine your algorithm a bit… Right now it looks a little too greedy…

You should modularize your programs a bit --separate the various functions. It would make your life a lot easier (by breaking the pieces of your code down into simpler bits).

Also, I suggest you use the vector class here.

Give me a short bit and I’ll respond again.

When programming, the most important thing you do has nothing to do with the computer. You must solve the problem first, on paper (I like construction paper and crayons…). This is RULE ONE. Nothing else you ever do will be as important as this rule.

Here is some help with organizing your program. Notice that one of the things I did was give really good names to your variables. One or two letter names like i, x, and q are almost always for nothing more than two-line throw-aways stuff. Don’t use them in the main design of your code!
Also, I’m using some C++ stuff here to get you accustomed to it. Feel free to use it --that’s how you learn.

Notice I’ve skipped all error checking… (you don’t need it for this assignment.)

``````#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;

using namespace std;

struct brick_t {
int area;
int position;
};

bool operator &lt; ( const brick_t &brick_a, const brick_t &brick_b ) {
// The std::sort() algorithm needs the 'less than' operator for the things it sorts
return brick_a.area &lt; brick_b.area;
}

int main() {
int             desired_wall_area;
int             number_of_bricks;
int             cntr;
vector&lt;brick_t&gt; bricks_available, bricks_used;
brick_t         temp;

// Input data
cin &gt;&gt; desired_wall_area;
cin &gt;&gt; number_of_bricks;

for (cntr = 0; cntr &lt; number_of_bricks; cntr++) {
temp.position = cntr;
cin &gt;&gt; temp.area;
bricks_available.push_back( temp );
}

// Sort the input in non-ascending order
sort( bricks_available.rbegin(), bricks_available.rend() );

// Determine which bricks to use here
...

// Output the results
cout &lt;&lt; bricks_used.size() &lt;&lt; endl;
for (cntr = 0; cntr &lt; bricks_used.size(); cntr++)
cout &lt;&lt; bricks_used[ cntr ].position;

return EXIT_SUCCESS;
}
``````

The main problem you are having is in the determination of which bricks fit in the wall.
Notice that I’ve added two vector objects to the program, one for the bricks that you can use, and the other for the bricks you actually did use. Your current algorithm does not account for this. The other thing is once you’ve put the bricks used in the second vector, you can use its length to determine how many bricks you used…

The problem with your algorithm is that it is too greedy. It works correctly up to the last
part, choosing the following bricks:
40
22
20
11
which add up to 93, leaving a remaining area of 100-93 = 7 to be filled. The remaining bricks available are
9
8
6
2
3
4
The next brick available less than or equal to 7 is 6, which your algorithm grabs, bringing the total area to 99, a difference from the target area of 1. The instructor’s solution skips 6, because 3 and 4 add to seven, which perfectly fills the desired area.

In other words, your algorithm does not consider all the possibilites of how to sum bricks, only one possibility. This is a common variation of “given a set of numbers, or pairs of numbers, or whatever, can some subset be drawn which adds to a desired number?”

Is this an algorithms class?
Do you need more pointers to solve this problem? Or have I given you enough to start?

Remember, you’ve got to be able to solve the problem with pencil and paper before you can tell the computer how to do it.

The problem with your algorithm is that it is too greedy. It works correctly up to the last
part, choosing the following bricks:
40
22
20
11
which add up to 93, leaving a remaining area of 100-93 = 7 to be filled. The remaining bricks available are
9
8
6
2
3
4
The next brick available less than or equal to 7 is 6, which your algorithm grabs, bringing the total area to 99, a difference from the target area of 1. The instructor’s solution skips 6, because 3 and 4 add to seven, which perfectly fills the desired area.

In other words, your algorithm does not consider all the possibilites of how to sum bricks, only one possibility. This is a common variation of “given a set of numbers, or pairs of numbers, or whatever, can some subset be drawn which adds to a desired number?”

First of all thanks for the help and advices Duoas.
What you mentioned is my problem ! My algorithm works only for a given set of numbers and not for pairs of numbers.
However I have not yet found how to solve it.

Google “knapsack problem” for pointers. (It’s an NP-complete problem.) If you still need help post again. Good luck!

One strategy to this so-called “knapsack problem” is one that is based on optimization techniques; see e.g. “Genetic Algorithms.”

This is a problem that, generally speaking, is not computable, but you can devise an algorithm that will seek an optimal (or at least “very good”) solution to it. For instance, suppose that you start by generating a pool of (say) ten possible solutions to the problem. Then, you select one and produce ten random variations of that solution, putting these into the pool. Furthermore, each time you attempt to produce ten random variations, you count the number of times that you produced (and threw away) randomly-chosen variant wasn’t suitable because it was too-big.

You “score” each of the (now, about 110) variations that are in your pool. You might score it based on its closeness to an optimal solution, and (perhaps) by the number of times a random solution based on this one went over-the-line, judging the latter event to be “a good thing.”

Now, you sort the pool by score and you randomly throw away 50% of the lower-half. And you repeat, watching to see if the algorithm converges on a solution.

SmaTheGreek, if you’re still stumped (NP-complete problems are notoriously difficult to solve --which makes them an odd favorite among introductory programming professors), here’s my solution.

I got out my pencil and paper and wrote down the numbers for the second test case:
40
22
20
11
9
8
6
4
3
2
Notice how I’ve sorted them like you did, largest to smallest. I only did this because it is easier to work with sorted lists than not.

Next, I used something of a functional language concept (which you have probably not studied): given a list of things

``````<b>xs</b> = <b>x:xs</b>
``````

This means I can define a list (xs) as an element (x) and a list (xs). This is recursive notation. In other words, the list [1, 2, 3, 4, 5] is defined as (1 (2 (3 (4 (5))))
/* functional geeks reading this, don’t give me grief about how this actually looks in <your favorite functional language>. Remember, KIS(S). */

What this means is that if I can do something to the first element in a list and a list then I can do it to the entire list. For example, a function that sums an integer list might be defined as

``````int sum( int *list, int length ) {
switch (length) {
case 0: return 0;
case 1: return *list;
default: return *list +sum( list +1, length -1 );
}
}
``````

We can organize our list of solutions the same way. For example, the number 14 can be made from our numbers by summing the list (2, (3, 9))).

Using this idea, I wrote out some solutions by hand: Numbers I have (areas of available bricks) go into the list with no summands, while composite brick areas have listed have their summands listed. I tracked composite summands by putting them in parentheses. Care was also taken to avoid using the same brick in the list of summands (since your input always has bricks of different areas. We can deal with multiple bricks of the same area later).

``````sum       summand1    summand2    list of summands
0         0           0
2                                 2
3                                 3
4                                 4
5         2           3           2,3
6                                 6
7         3           4           3,4
8                                 8
9                                 9
10        8           2           8,2
11                                11
12        9           3           9,3
13        (10)        3           8,2, 3
14        (12)        2           9,3, 2
15        11          4           11, 4
16        9           (7)         9, 3,4
17        11          6           11, 6
18        11          (7)         11, 3,4
19        11          8           11, 8
20                                20
21        11          9           11, 9
22                                22
23        (21)        2           11,9, 2
24        (21)        3           11,9, 3
25        (21)        4           11,9, 4
26        (24)        2           11,9,3, 2
27        (25)        2           11,9,4, 2
28        (25)        3           11,9,4, 3
29        (23)        6           11,9,2, 6
30        (28)        2           11,9,4,3, 2
31        (24)        6           11,9,3,2, 6
32        (29)        3           11,9,2,6, 3
33        (29)        4           11,9,2,6, 4
34        (28)        6           11,9,4,3, 6
35        (31)        4           11,9,3,2,6, 4
36        (34)        2           11,9,4,3,6, 2
37        (29)        8           11,9,2,6, 8
38        (30)        8           11,9,4,3,2, 8
...
``````

By now the sums were getting a little large and a pattern emerged as to how I was solving the problem. I noticed that the right summand (summand2) was always a small number counting up through the available sums, while the left summand (summand1) was usually a composite sum.

It turns out that this method is the solution. All you need to do is build a list until sum == the wall area or you run out of bricks (whichever comes first). Then pick the highest sum off the top and reconstruct your wall:
If your target wall area were 38, then run through the list of composite sums recursively, storing non-composite sums in the list of bricks_used. This even suggests a data structure to use:

``````struct sum_t {
int sum, summand1, summand2;
}
``````

You’ll spend some time searching through lists (some of that time can be removed by turning summands into indices into the list of sums).

In this case, C++ is your friend.

``````#include &lt;algorithm&gt;
#include &lt;vector&gt;
using namespace std;

struct sum_t {
int sum, summand1, summand2;
sum_t( int s = 0, int s1 = 0, int s2 = 0 ):
sum( s ),
summand1( s1 ),
summand2( s2 ) { }
}

bool operator == ( const sum_t &sum1, const sum_t &sum2 ) {
// The std::find() algorithm needs this operator on type sum_t
return sum1.sum == sum2.sum;
}

int main() {
vector&lt;sum_t&gt; sum_list;

...
// The algorithm works best if we sort the numbers in <i>non-descending order</i>
sort( bricks_available.begin(), bricks_available.end() );
...

// find a specific sum (int sum_to_find) in the sum_list vector
int index_of_summand = find(
sum_list.begin(),
sum_list.end(),
sum_t( sum_to_find )
)
-sum_list.begin();

if (index_of_summand &lt; sum_list.size()) then you've found a valid index.

...
}
``````

Hope this helps.

as I can see you have some experience in c++ so I hope somebody can help me…my problem or my question is : You maybe know that it is possible to modify the xbox controller and attach it via usb to computer … and there are these xbcd drivers http://www.redcl0ud.com/xbcd.html and there is the option to modify the source code, so the point of my question is how can you control via c++ the rumble feature ? … I am totally noob … I hope somebody can help me … or maybe not … thanks for your help in advance

Sorry to say it, but I think you are in WAY over your head (with ocean liners and submarines passing overhead).

I know nothing about the XBOX or rumble controlers. What you are looking to do is modify device drivers, which means you must know a fair amount about the hardware you are working with: what ports to read, when, and what the bit values you get and send through them mean.

C++ seems a bit of an overkill for a device driver to me… must be some fancy stuff it can do.

Also, I just tested my solution above and it needs a little work still… :o
Perhaps a more expansive tree for all summand possibilities would work better than the thing I did (which turns out to be just what SmaTheGreek did: arbitrarily choose one path over many…).

Foo.

Well, Sma, ask your professor how he expects you to get the correct answer. If you still need help I’ll see if I can’t improve my solution but for now I’m done with it (I have homework too…).

mhh :o you mean this ? http://euc.jp/periphs/xbox-controller.en.html

Like Duoas said, you’re trying to jump into the very deep end of the pool … err ocean.

(I don’t know anything about programming Xbox’s either.)

But programming hardware device drivers is in the same league as writing a compiler program or maybe even modifying Blender source code You’re better off looking around for someone who has already written the program/driver modifciation.

Or if you’re really determined, check out some Xbox / game / hardware programming forums or UseNet.

Mike

Thanks for the help Duoas. Well the problem could be solved with a dynamic programming approach, but my solution was accepted as an approximation solution(actually this program was for a school contest).This happened as the aim of the 1st phase of the contest was to allow as more participants to pass to the 2nd phase as possible.However many participants did not know how to work with dynamic programming and as a result the organizers of the contest decided to accept approximation solutions like mine
So it is ok now, I’ve passed the first phase! Thanks for the help guys.