Knapsack algorithm easy to implement, the input form is as follows:
Backpack capacity: 20
Item number: 10
Item weight: 1 3 5 6 7 8 10 12 13 14
The combination of output can fill backpacks,
Using C language implementation
Great god help me, I just learning data structure
CodePudding user response:
Baidu keyword!!!!!!CodePudding user response:
https://blog.csdn.net/xuqi7/article/details/72477996The inside write very simple, can make a little change
CodePudding user response:
# include & lt; stdio.h>
# include & lt; Stdlib. H>
# include & lt; String. H>
Typedef struct bag_t
{
Int * items;
Int item_num;
Int item_max;
Int weight;
Int weight_max;
} bag;
/*
* add a item with specific weight
* return: 0 ok, 1 failed
* */
Int add_item (bag * b, int weight)
{
If (weight + b - & gt; Weight & gt; B - & gt; Weight_max)
return -1;
If (b - & gt; Item_num==b - & gt; Item_max) {//the number of expansion, expansion and not weight (capacity)
Int * TMP=(int *) realloc (b - & gt; The items, 2 * b - & gt; Item_max);
If (TMP==NULL) {
Printf (" realloc failed \ n ");
The exit (1);
}
B - & gt; The items=TMP;
B - & gt; Item_max=2 * b - & gt; Item_max;
}
//add
B - & gt; Weight +=weight;
B - & gt; The items [b - & gt; item_num + +]=weight;
return 0;
}
'the * create_bag (int weight_max)
{
Bag * b=(bag *) malloc (sizeof (bag);
if(! B)
return NULL;
Memset (b, 0, sizeof (bag);
B - & gt; Item_max=10;
B - & gt; The items=(int *) malloc (sizeof (int) * b - & gt; Item_max);//the default create 10, is used to record data, expansion and subsequent automatically according to need
if(! B - & gt; The items) {
Free (b);
return NULL;
}
B - & gt; Weight_max=weight_max;
}
Void print_bag (bag * b)
{
if(! B)
return;
int i;
Printf (" ");
For (I=0; I & lt; B - & gt; Item_num; I++) {
Printf (" % d, b - & gt; The items [I]);
}
Printf ("] \ n ");
}
Void clear_bag (bag * b)
{
if(! B)
return;
B - & gt; Item_num=0;
B - & gt; Weight=0;
}
* * BPTR void destroy_bag (bag)
{
'the * b=* BPTR;
if(! B) {
if(! B - & gt; The items) {
Free (b - & gt; The items);
B - & gt; The items=NULL;
}
Free (b);
B=NULL;
}
}
Void check_weight_ok (bag * b)
{
Static int I=1;
If (b - & gt; Weight==b - & gt; Weight_max) {
Printf (" % d [combination] : ", i++);
Print_bag (b);
}
}
Fixed a start/* start1, follow-up since start2 add
Looking for failure, skip start2, from start2 + 1 to
*/
Void pick2bag (bag * b, int a [], int start1, int start2, int idmax)
{
Clear_bag (b);
Add_item (b, a, [start1]).
If (start1==idmax) {
Check_weight_ok (b);
return;
}
If (start2 & gt; Idmax)
return ;
For (int I=start2; I & lt;=idmax; I++) {
Int rt=add_item (b, a [I]);
If (rt!=0) {
Check_weight_ok (b);
break;
}
}
Pick2bag (b, a, start1, start2 + 1, idmax);
}
Int main ()
{
Int test [10]={1, 3, 5, 6, 7, 8, 10, 12, 13, 14};
'the * b=create_bag (20);//create the capacity to 20 weight (hold) the backpack
if(! B) {
Printf (" create_bag failed \ n ");
return -1;
}
Int n=sizeof (test)/sizeof (test [0]).
Int idmax=n - 1;
For (int I=0; I & lt;=idmax; I++) {
Pick2bag (b, the test, I, I + 1, idmax);
}
Destroy_bag (& amp; B);
return 0;
}
Hand in the homework
CodePudding user response:
The