Backpack problem: There are different value, different weight items n pieces. Select a part in this item is that the total weight of the selected item does not exceed the designated weight, but the total value of the item is the largest.
Solution ideas: All possible use of the item selected, will meet the restriction weight conditions, Value has always stored the maximum total value of the item, and weight is the total weight of the conditions that meet the conditions, the following is my own written A code, the idea of the "System Designer" tutorial, the code is compiled, and the results are correct: #include #include #define max 100struct Bag {INT Weight; int value;} Bag [max]; int A [max]; int value = 0; int Weight; int COMB (Int m, int K) {INT I, J; Int Wei, Val; for (i = m ; i> = k; I -) {a [k] = i; if (k> 1) COMB (I-1, K-1); Else {wei = 0; // Pred value 0 VAL = 0; For (j = a [0]; j> 0; j -) // Each combination requests their weight and value {Wei = wei bag [a [j]]. weight; VAL = VAL BAG [ a [j]]. value;} if (wei <= weight && val> value) // determines if the condition is met VALUE = Val;}} Return Value;} void main () {Int Num, Subnum; int L, CLRSCR (); Printf ("/ NENTER THE NUMBER OF TOTAL BAG:"); // Enter the total number of SCANF ("% D", & Num); Printf ("/ NENTER% D Number Bag'Weight and Bag ' Value (Sample *, *) / N ", NUM); // Enter the weight and value for the backpack for (L = 1; L <= NUM; L ) Scanf ("% D,% D ", & Bag [L]. Weight, & Bag [L] .value); Printf ("/ NENTER THE SUBNUMBER OF THE BAG:"); // Enter the number of Scanf ("% D", & subnum) required for the backpack; Printf ("/ NENTER THE Weight For% D Bag:", Subnum); // Enter the weight Scanf ("% D", & weight,,, & weight ); A [0] = Subnum; Printf ("/ nthe max value is:% d", comb (num, subnum)); getch ();} summary: When you look at the example of the reference book, you should make more brains. I want to think about it first. Among the comparison, it is very helpful to yourself.
