[C/C++ 演算法]- 背包問題（Knapsack Problem）
剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。
拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/KnapsackProblem.htm
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 8 // 重量限制
typedef struct {
char name[20];
int weight;
int price;
} Fruit;
void knapsack(Fruit*, int*, int*, int, int);
int min(Fruit*, int);
int main(void) {
Fruit fruits[] = {{"李子", 4, 4500},
{"蘋果", 5, 5700},
{"橘子", 2, 2250},
{"草莓", 1, 1100},
{"甜瓜", 6, 6700}};
int items[LIMIT + 1] = {0};
int values[LIMIT + 1] = {0};
int length = sizeof(fruits) / sizeof(fruits[0]);
knapsack(fruits, values, items, length, LIMIT);
printf("物品\t價格\n");
int i;
for(i = LIMIT; i >= min(fruits, length); i -= fruits[items[i]].weight) {
printf("%s\t%d\n", fruits[items[i]].name, fruits[items[i]].price);
}
printf("合計\t%d\n", values[LIMIT]);
return 0;
}
void knapsack(Fruit* fruits, int* values, int* items,
int length, int limit) {
int i, w;
for(i = 0; i < length; i++) {
for(w = fruits[i].weight; w <= limit; w++) {
int p = w - fruits[i].weight;
int newValue = values[p] + fruits[i].price;
if(newValue > values[w]) { // 找到階段最佳解
values[w] = newValue;
items[w] = i;
}
}
}
}
int min(Fruit* fruits, int length) {
int i, m;
for(i = 0, m = fruits[0].weight; i < length; i++) {
if(fruits[i].weight < m) {
m = fruits[i].weight;
}
}
return m;
}
|
沒有留言:
張貼留言