實作簡單背包演算法，輸入形式如下：
背包容量：20
物品個數：10
物品重量：1 3 5 6 7 8 10 12 13 14
輸出能夠裝滿背包的組合。
用C語言實作
大神幫幫忙，我剛學資料結構
uj5u.com熱心網友回復：
百度關鍵詞！！！uj5u.com熱心網友回復：
https://blog.csdn.net/xuqi7/article/details/72477996這個里面寫的很淺顯易懂，稍作修改就能用
uj5u.com熱心網友回復：
#include <stdio.h>
#include <stdlib.h>
#include <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->weight > b->weight_max)
return -1;
if(b->item_num == b->item_max){ //個數擴容，并不是重量（容量）擴容
int *tmp = (int*)realloc(b->items, 2 * b->item_max);
if(tmp == NULL){
printf("realloc failed\n");
exit(-1);
}
b->items = tmp;
b->item_max = 2 * b->item_max;
}
//add
b->weight += weight;
b->items[b->item_num++] = weight;
return 0;
}
bag *create_bag(int weight_max)
{
bag *b = (bag*)malloc(sizeof(bag));
if(!b)
return NULL;
memset(b, 0, sizeof(bag));
b->item_max = 10;
b->items = (int*)malloc(sizeof(int) * b->item_max); //默認創建10個,用來記錄資料,后續根據需要自動擴容
if(!b->items){
free(b);
return NULL;
}
b->weight_max = weight_max;
}
void print_bag(bag *b)
{
if(!b)
return;
int i;
printf("[ ");
for(i = 0; i < b->item_num; i++){
printf("%d ", b->items[i]);
}
printf("]\n");
}
void clear_bag(bag *b)
{
if(!b)
return;
b->item_num = 0;
b->weight = 0;
}
void destroy_bag(bag **bptr)
{
bag *b = *bptr;
if(!b){
if(!b->items){
free(b->items);
b->items = NULL;
}
free(b);
b = NULL;
}
}
void check_weight_ok(bag *b)
{
static int i = 1;
if(b->weight == b->weight_max){
printf("[組合%d]: ", i++);
print_bag(b);
}
}
/* 固定一個開始start1，后續從start2開始加
尋找失敗，則跳過start2， 從start2+1繼續
*/
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 > idmax)
return ;
for(int i = start2; i <= 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};
bag *b = create_bag(20); //創建容量為20（容納重量）的背包
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 <= idmax; i++){
pick2bag(b, test, i, i+1, idmax);
}
destroy_bag(&b);
return 0;
}
交作業了
uj5u.com熱心網友回復：
你這個代碼還有bug啊。。
uj5u.com熱心網友回復：
？？？？？？uj5u.com熱心網友回復：
uj5u.com熱心網友回復：
你看提示，要么你在編譯選項加-std=c99或者-std=c11
默認沒有開啟這個選項，老古董的編譯模式，默認是c89的，89年的標準，現在都2020年了
要么你把for(int i = start2; i <= idmax; i++) //c89不支持這種格式的語法
把這個i提到for的括號外來
變成
int i;
for(i = start2; i <= idmax; i++)
=========
我的建議，你的編譯器應該是哪里可以配置的吧，把編譯選項默認加-std=c99或者 -std=c11
畢竟要與時俱進吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/88690.html
標籤：C語言
上一篇：跪求大神指點！
下一篇：員工管理系統遇到的問題，不懂