Find max valuable item val from multiple items, algorithm

LmaverickD (54)
For everyone who had gotten me to this point, I'm really grateful. Learn a lot from you guys.
I posted this question before, I got everything running and the post seems a bit messy since I have to redo almost everything from there.
the previous post:http://www.cplusplus.com/forum/beginner/273757/

It seems that something wrong with my algorithm.
I'm not sure which part. I have gone through this so many times and didn't find where it went wrong.

my program supposed to: create a program with Dynamic programming.

A burglar has broken into a jewelry store to steal. He can only carry out a certain amount of stuff before it gets too heavy. In addition, he can only make one trip in and out of the store before the cops arrive, so he wants to be sure to get the most value out of the stuff he takes. Input for the program will be as below. The first line will contain how much he can carry. This line is followed by a single item per line. Each of these lines will contain the name of the item, the number of items available, each individual item’s weight, and its value. There will be up to 10 different items. Output the number of each item type he should take to maximize his value as well as the max value.

100
Pearl 1 25 10
Ruby 4 40 12
Diamond 5 30 15
Emerald 10 5 10
Sapphire 1 50 20

The output should be printed as:
10 Emerald, 1 Sapphire 120

the current output that I got:
1Diamond,10Emerald,115


my post previously. everything is pretty much almost the same beside the loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
void dynamicProg(Item* arr, int itemType, int totalWeight)
{
        int previousBest, newItemInc, row;
	int totalItem = 0;
	for (row = 0; row < itemType; row++) totalItem += arr[row].Quantity;
	int** optTable = new int* [totalItem + 1];
	for (row = 0; row < totalItem + 1; row++) optTable[row] = new int[totalWeight + 1];
	
	//setup item IndexTable
	Item** itemIndexTable = new Item * [totalItem + 1];
	int col = 1;
	for (row = 0; row < itemType; row++) {
		int count = arr[row].Quantity;
		while (count > 0) {
			itemIndexTable[col++] = &arr[row];
			count--;
		}
	}//0 to the first row
	for (row = 0; row < totalWeight; row++) { 
		optTable[0][row] = 0; 
	}
	for (row = 1; row < totalItem + 1; row++) {
		for (col = 0; col < totalWeight + 1; col++) {
			if (col - itemIndexTable[row]->Weight > 0) {
				//copy val
				previousBest = optTable[row - 1][col];
				newItemInc = optTable[row - 1][col - itemIndexTable[row]->Weight] + itemIndexTable[row]->Value;
				if (previousBest > newItemInc) {
					optTable[row][col] = previousBest;
				}
				else {
					optTable[row][col] = newItemInc;
				}
			}
			else {
				//cant conclude the cur item
				optTable[row][col] = optTable[row - 1][col];
			}
		}
	}
	//retrace rows and col = shrink
	int currentRow = totalItem;
	int currentCol = totalWeight;
	while (currentRow > 0 && currentCol > 0) {
		if (optTable[currentRow][currentCol] == optTable[currentRow - 1][currentCol]) {
			currentRow--;
		}
		else {
			currentCol -= itemIndexTable[currentRow]->Weight;
			itemIndexTable[currentRow]->taken++;
			currentRow--;
		}
	}
	itemIndexTable[row]->Quantity, itemIndexTable[row]->Name, itemIndexTable[row]->Value;
        //print loop
	for (int row = 0; row < itemType; row++) {
		if (arr[row].taken > 0) {
			cout << arr[row].taken << "" << arr[row].Name << ",";
		}
	}
	cout << optTable[totalItem][totalWeight];
}
Last edited on
coder777 (8450)
So first: Why all this dynamic arrays? There are up to 10 items hence an fixed size array would suffice.

I would guess this task implies the greedy algorithm. This means you need to (bubble?) sort the array according to the value.

The next step would be:

Take as many of the first item (not exceeding the weight limit/number). Then take the second etc.

You need two loops: One outer for each items, one inner for the item count. I suggest a second [fixed sized=10] array (which contains number of items use) and that type:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
// sort item array

int taken[10]{0};
remain_weight = max_weight; //e.g. 100
for(int i = 0; i < item_count; ++i)
{
  for(int j = 0; j < item[i].count; ++j)
  {
    if(item[i].weight < remain_weight)
    {
      remain_weight -= item[i].weight;
      ++taken[i];
    }
    else
      break;
  }
}

// print item where taken[i] != 0


When you have it sorted and those simple two loops you would get the result as it should.
ne555 (10692)
> Why all this dynamic arrays? There are up to 10 items hence an fixed size array would suffice.
agreed, ¿what's the max weight? if it actually doesn't fit on the stack, use std::vector so we don't have to analyse your memory management (by the way, you don't have any delete)

may also explode your function into initialization, dynamic programming and output, to ease the debugging


> I would guess this task implies the greedy algorithm.
no, dynamic programming
a greedy algorithm will not give you the best result. you may test it on the example case,
choosing by value give you:
1 sapphire, 1 diamond, 4 emerald, for a total of 75


@OP: your error is on line 24 if (col - itemIndexTable[row]->Weight > 0)

about style
1
2
3
 
	for (row = 0; row < totalWeight; row++) { 
		optTable[0][row] = 0; 
	}
limit scope, may write for(int row = 0; //...
don't overload the meaning of your variables, you are using `row' to traverse the columns
just as variable names, comments are for programmers, make sure they are correct and DEA «cant conclude the cur item» -> «can't include current item»
line 54: itemIndexTable[row]->Quantity, itemIndexTable[row]->Name, itemIndexTable[row]->Value; that's no operation, ¿what was the intent?
avoid input/output in functions (unless their only purpose is to input/output), return the value and let main() do the printing, otherwise your function loses communication and becomes useless
(perhaps later the dynamic programming is only a step in the algorithm)
Last edited on
coder777 (8450)
¿what's the max weight?
It's the first value of the input data.

Yeah, greedy seems a bit too simply for this.
LmaverickD (54)
@coder777: I was told to create it with a knapsack instead of greedy. The algorithm that I have currently is from the discussion we have in class. I use dynamic arr just in case if the instructor will use different input values.

@ne555 how do I fix line 24? because all it compares if it's bigger than 0 then it would copy the value from the previous best value it got? or the next best value

So it would best to use something generic variable as I or j instead of row?

I see what you mean in line 54. I deleted that line and also put 
//delete arr
	for (row = 0; row < totalItem + 1; row++) {
		delete[] optTable[row];
	}
	delete[] optTable;
	delete[] itemIndexTable;
}

LmaverickD (54)
So I got an excel spreadsheet to compare it.
When I debug it, my row =21 and col 101. it supposed to have 22 rows and when I compare it to the spreadsheet it's why I'm getting 115 since the last row supposed to contain 120. I'm not sure where it went wrong. since everything is consist of dynamic arr, to begin with
jonnin (11497)
excel has 1..n rows shown and talks about them this way, and c++ has 0..n-1 rows and talks about them that way, right? SO its not that?

that aside one way to do it is to assign a new value of value/weight to each item. You still can't use greedy entirely, but it can weed out unlikely combinations perhaps?
pure greedy off ratios is 115: 10E + 1D, so if its 120 that won't do it. the code would have to realize that with 20 extra pounds left that 1S will fit even if its not the ideal pick (if you had more space left). And that is likely not the only scenario where greedy bites you.
Last edited on
againtry (2313)
I decided to persist despite not being all that familiar with the knapsack.

The result doesn't seem to be right but at least I can get it to run through the whole f'kin inventory. I would have preferred the meaning of life answer to be 42 but I'll settle for 120 if I have to.

For testing purposes the sample file would have to be about the worst choice anybody could make. A much simpler one is my next, and there are plenty of demos around to benchmark before this one at 100 is any use for test/debug. Just make one up.

BTW 'taken' as a data member is irrelevant AFAICS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>

struct Item
{
    std::string Name{"No name"};
    int Quantity{0};
    int Weight{0};
    int Value{0};
};

std::ifstream& operator>> (std::ifstream& lhs, Item& rhs)
{
    lhs >> rhs.Name;
    lhs >> rhs.Quantity;
    lhs >> rhs.Weight;
    lhs >> rhs.Value;
    return lhs;
}

std::ostream& operator<<(std::ostream& os, const Item& item)
{
    os
    << "Name: " << std::setw(10) << item.Name << std::setw(4)
    << " Qty: " << item.Quantity << " Wt: " << item.Weight
    << " Val: " << item.Value;
    
    return os;
}


void display_stock(Item* st, int n)
{
    for(int i = 0; i < n; i++)
    std::cout << st[i] << '\n';
}

std::string heading()
{
    return "      NAME QTY  WT VAL";
}

// MAXIMUM OF TWO INTEGERS
int max(int a, int b)
{
    return (a > b) ? a : b;
}

int main()
{
    // READ FILE
    std::ifstream infile("item_01.txt");
    int MAX_WEIGHT = 0;
    infile >> MAX_WEIGHT;
    
    // COUNT NO. OF ITEMS
    Item temp;
    int NO_OF_CATALOG_ITEMS = 0;
    while (infile >> temp)
    {
        NO_OF_CATALOG_ITEMS++;
    }
    std::cout <<
    "  No. of items in stock: " << NO_OF_CATALOG_ITEMS << '\n';
    
    Item* Stock = new Item[NO_OF_CATALOG_ITEMS];
    
    // GO BACK TO START OF FILE
    infile.clear();
    infile.seekg(0);
    
    
    // RE-READ FIRST LINE
    infile >> MAX_WEIGHT;
    std::cout <<
    "Maximum weight to carry: " << MAX_WEIGHT << '\n';
    
    
    // RE-READ REMAINDER OF FILE INTO ARRAY
    for(int i = 0; i < NO_OF_CATALOG_ITEMS; i++)
    {
        infile >> Stock[i];
    }
    infile.close();
    
    
    // PREPARE A LIST OF ITEMS ITEM BY ITEM
    int NO_OF_ITEMS{0};
    for(int i = 0; i < NO_OF_CATALOG_ITEMS; i++)
    {
        NO_OF_ITEMS += Stock[i].Quantity;
    }
    std::cout << "     Total no. of items: " << NO_OF_ITEMS;
    
    
    // SETUP & FILL ITEMIZED INVENTORY
    Item* Inventory = new Item[NO_OF_ITEMS + 1];
    
    Item Dummy;
    Inventory[0] = Dummy;
    
    int count{1};
    for(int i = 0; i < NO_OF_CATALOG_ITEMS; i++)
    {
        temp = Stock[i];
        for(int j = 0; j < temp.Quantity; j++ )
        {
            Inventory[count] = temp;
            count++;
        }
    }
    
    int **T = new int*[NO_OF_ITEMS + 1];
    for(int row = 0; row < NO_OF_ITEMS +1; ++row)
    {
        T[row] = new int[MAX_WEIGHT + 1];
    }
    
    
    // INITIALIZE MATRIX
    for (int i = 0; i < NO_OF_ITEMS + 1; i++)
    {
        for (int j = 0; j < MAX_WEIGHT + 1; j++)
        {
            T[i][j] = 0;
        }
    }
    
    // T[][] TABLE
    for (int i = 0; i < NO_OF_ITEMS + 1; i++)
    {
        if(i > 0)  // DON'T PRINT DUMMY
        {
            std::cout << "Item no: " << i << '\t' << Inventory[i] << '\n';
        }
        
        count = 1; // FORMAT OUTPUT PURPOSES
        for (int j = 0; j < MAX_WEIGHT + 1; j++)
        {
            if (i == 0 || j == 0)
                T[i][j] = 0;
            else if(j < Inventory[i].Weight)
                T[i][j] = T[i-1][j];
            else
                T[i][j] = max( Inventory[i].Value +
                              T[i - 1][j - Inventory[i].Weight],
                              T[i - 1][j] );
            
            if(i > 0) // DON'T PRINT DUMMY
                std::cout << T[i][j] << ' ';
            
            if(count++ % 20 == 0)
                std::cout << '\n';
        }
        std::cout << "\n\n";
    }
    
    std::cout << "ANSWER: " << T[NO_OF_ITEMS][MAX_WEIGHT] << '\n';
    
    
    // CLEANUP DYNAMIC ARRAYS
    delete[] Stock;
    Stock = nullptr;
    
    delete[] Inventory;
    Inventory = nullptr;
    
    for(int i = 0; i < NO_OF_ITEMS + 1; ++i)
    {
        delete [] T[i];
    }
    delete [] T;
    T = nullptr;
    
    return 0;
}


EDIT: final cut
Last edited on
againtry (2313)
  No. of items in stock: 5
Maximum weight to carry: 100
     Total no. of items: 21






Item no: 1	Name:      Pearl Qty: 1 Wt: 25 Val: 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
10 

Item no: 2	Name:       Ruby Qty: 4 Wt: 40 Val: 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 
12 12 12 12 12 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 
22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 
22 

Item no: 3	Name:       Ruby Qty: 4 Wt: 40 Val: 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 
12 12 12 12 12 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 
24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 
24 

Item no: 4	Name:       Ruby Qty: 4 Wt: 40 Val: 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 
12 12 12 12 12 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 
24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 
24 

Item no: 5	Name:       Ruby Qty: 4 Wt: 40 Val: 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 
12 12 12 12 12 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 
24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 
24 

Item no: 6	Name:    Diamond Qty: 5 Wt: 30 Val: 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 15 15 15 15 15 15 15 15 15 15 
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 25 25 25 25 25 
25 25 25 25 25 25 25 25 25 25 27 27 27 27 27 27 27 27 27 27 
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 37 37 37 37 37 
37 

Item no: 7	Name:    Diamond Qty: 5 Wt: 30 Val: 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 15 15 15 15 15 15 15 15 15 15 
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 25 25 25 25 25 
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 
30 30 30 30 30 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 
42 

Item no: 8	Name:    Diamond Qty: 5 Wt: 30 Val: 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 15 15 15 15 15 15 15 15 15 15 
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 25 25 25 25 25 
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 
30 30 30 30 30 40 40 40 40 40 45 45 45 45 45 45 45 45 45 45 
45 

Item no: 9	Name:    Diamond Qty: 5 Wt: 30 Val: 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 15 15 15 15 15 15 15 15 15 15 
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 25 25 25 25 25 
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 
30 30 30 30 30 40 40 40 40 40 45 45 45 45 45 45 45 45 45 45 
45 

Item no: 10	Name:    Diamond Qty: 5 Wt: 30 Val: 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 10 10 10 10 10 15 15 15 15 15 15 15 15 15 15 
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 25 25 25 25 25 
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 
30 30 30 30 30 40 40 40 40 40 45 45 45 45 45 45 45 45 45 45 
45 

Item no: 11	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
10 10 10 10 10 10 10 10 10 10 20 20 20 20 20 25 25 25 25 25 
25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 
35 35 35 35 35 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 
40 40 40 40 40 40 40 40 40 40 50 50 50 50 50 55 55 55 55 55 
55 

Item no: 12	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 20 20 20 20 20 
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 
35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 
35 35 35 35 35 45 45 45 45 45 50 50 50 50 50 50 50 50 50 50 
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 60 60 60 60 60 
65 

Item no: 13	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 
40 40 40 40 40 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 
45 45 45 45 45 45 45 45 45 45 55 55 55 55 55 60 60 60 60 60 
60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 
70 

Item no: 14	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 
40 40 40 40 40 50 50 50 50 50 55 55 55 55 55 55 55 55 55 55 
55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 65 65 65 65 65 
70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 
70 

Item no: 15	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 
50 50 50 50 50 50 50 50 50 50 60 60 60 60 60 65 65 65 65 65 
65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 
75 75 75 75 75 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 
80 

Item no: 16	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 60 60 60 60 60 60 60 60 60 60 
60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 70 70 70 70 70 
75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 
75 75 75 75 75 85 85 85 85 85 90 90 90 90 90 90 90 90 90 90 
90 

Item no: 17	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 60 60 60 60 60 70 70 70 70 70 
70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 
80 80 80 80 80 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 
85 85 85 85 85 85 85 85 85 85 95 95 95 95 95 100 100 100 100 100 
100 

Item no: 18	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 60 60 60 60 60 70 70 70 70 70 
80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 
80 80 80 80 80 90 90 90 90 90 95 95 95 95 95 95 95 95 95 95 
95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 105 105 105 105 105 
110 

Item no: 19	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 60 60 60 60 60 70 70 70 70 70 
80 80 80 80 80 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 
90 90 90 90 90 90 90 90 90 90 100 100 100 100 100 105 105 105 105 105 
105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 
115 

Item no: 20	Name:    Emerald Qty: 10 Wt: 5 Val: 10
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 60 60 60 60 60 70 70 70 70 70 
80 80 80 80 80 90 90 90 90 90 100 100 100 100 100 100 100 100 100 100 
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 110 110 110 110 110 
115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 
115 

Item no: 21	Name:   Sapphire Qty: 1 Wt: 50 Val: 20
0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30 30 30 30 
40 40 40 40 40 50 50 50 50 50 60 60 60 60 60 70 70 70 70 70 
80 80 80 80 80 90 90 90 90 90 100 100 100 100 100 100 100 100 100 100 
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 110 110 110 110 110 
115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 
120 

ANSWER: 120
Program ended with exit code: 0
Last edited on
againtry (2313)
BTW Before the C++ police leap out of their corner, some of this can be refined obviously by passing around pointers, smart ones even, <vector>'s, <array>'s and/or other STL containers. I had other fish to fry but they are free to jump into the frypan :)
LmaverickD (54)
@againtry once again you safe the day! Thank you. I figure out what went wrong.
againtry (2313)
@LmaverickD, Be careful with it though. It runs and gives the right answer but there are a couple of almost intractable bloopers that need correcting.

EDIT: FWIW it is now tested and runs properly as above and with other data. This is so obviously much better suited to STL workmanship standards I might do it despite not having a complete handle on deciphering the results.
Last edited on
Topic archived. No new replies allowed.