https://download.csdn.net/download/SQ_ZengYX/88620871文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-784892.html
搜索與回溯
#include <iostream>
using namespace std;
#define N 100
int n;
double limitW;
double maxv;
int option[N];
int cop[N];
struct {
double weight;
double value;
} a[N];
void BackTrack(int i, double tw, double tv) {
// 不能超出重量限制
if (tw > limitW + 0.1)
return;
if (tv > maxv) {
for (int k = 0; k < n; ++k)
option[k] = cop[k];
maxv = tv;
}
// 選第i個(gè)物品
cop[i] = 1;
if (i < n)
BackTrack(i + 1, tw + a[i].weight, tv + a[i].value);
// 不選第i個(gè)物品
cop[i] = 0;
if (i < n)
BackTrack(i + 1, tw, tv);
}
int main() {
int k;
double w[N], v[N];
cout << "輸入物品種數(shù):" << endl;
cin >> n;
cout << "輸入限制重量:" << endl;
cin >> limitW;
for (k = 0; k < n; ++k) {
cout << "依次輸入第" << k + 1 << "個(gè)物品的重量和價(jià)值: " << endl;
cin >> w[k] >> v[k];
a[k].weight = w[k];
a[k].value = v[k];
}
maxv = 0.0;
for (k = 0; k < n; ++k)cop[k] = 0;
BackTrack(0, 0.0, 0.0);
cout << "所選物品為：" << endl;
for (k = 0; k < n; ++k)
if (option[k])
cout << k + 1 << "\t";
cout << endl << "總價(jià)值為:" << maxv << endl;
}動(dòng)態(tài)規(guī)劃
#include<iostream>
using namespace std;
int weight[100], goods_value[100];//weight表示背包可容納重量，godds_value表示物品價(jià)值
int Value[100][100];//價(jià)值數(shù)組
int ZeroOneBag(int goods_value[], int weight[], int Value[][100], int m, int n) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j < weight[i]) {
Value[i][j] = Value[i - 1][j];
} else if (Value[i - 1][j] >= (Value[i - 1][j - weight[i]] + goods_value[i])) {
Value[i][j] = Value[i - 1][j];
} else {
Value[i][j] = Value[i - 1][j - weight[i]] + goods_value[i];
}
}
}
return Value[m][n];
}
int main() {
int i = 0, m, n, value = 0;
cout << "請(qǐng)輸入物品個(gè)數(shù)：" << endl;
cin >> m;
cout << "請(qǐng)輸入背包容量：\n";
cin >> n;
for (i = 1; i <= m; i++) {
cout << "請(qǐng)輸入物品" << i << endl;
cout << "重量: " << "價(jià)值: \n";
cin >> weight[i] >> goods_value[i];
}
value = ZeroOneBag(goods_value, weight, Value, m, n);
cout << "背包能容納的最大價(jià)值為：" << value << endl;
cout << endl;
}
貪心
#include <iostream>
#include<algorithm>
using namespace std;
struct goodinfo {
float p; //物品效益
float w; //物品重量
float X; //物品該放的數(shù)量
int flag; //物品編號(hào)
bool operator<(goodinfo b) {
return p > b.p;
}//按物品效益，重量比值做升序排列
};//物品信息結(jié)構(gòu)體
void bag(goodinfo goods[], float M, int n) {
float cu;
int i, j;
for (i = 1; i <= n; i++)
goods[i].X = 0;
cu = M; //背包剩余容量
for (i = 1; i < n; i++) {
if (goods[i].w > cu) //當(dāng)該物品重量大與剩余容量跳出
continue;
goods[i].X = 1;
cu = cu - goods[i].w; //確定背包新的剩余容量
}
//按物品編號(hào)做降序排列
for (j = 2; j <= n; j++) {
goods[0] = goods[j];
i = j - 1;
while (goods[0].flag < goods[i].flag) {
goods[i + 1] = goods[i];
i--;
}
goods[i + 1] = goods[0];
}
cout << "最優(yōu)解為:" << endl;
double ans = 0;
for (i = 1; i <= n; i++) {
cout << "第" << i << "件物品要放:";
cout << goods[i].X << endl;
ans += goods[i].p * goods[i].w * goods[i].X;
}
cout << "總價(jià)值為：" << ans << endl;
}
int main(void) {
cout << "|--------運(yùn)用貪心法解背包問(wèn)題---------|" << endl;
cout << "|-------------------------------------|" << endl;
int i, n;
float M;
cout << "請(qǐng)輸入物品的總數(shù)量：";
cin >> n;
cout << "請(qǐng)輸入背包的最大容量：";
cin >> M;
goodinfo goods[n + 1];
cout << endl;
for (i = 1; i <= n; i++) {
goods[i].flag = i;
cout << "請(qǐng)輸入第" << i << "件物品的重量:";
cin >> goods[i].w;
cout << "請(qǐng)輸入第" << i << "件物品的效益:";
cin >> goods[i].p;
goods[i].p = goods[i].p / goods[i].w; //得出物品的效益，重量比
cout << endl;
}
sort(goods + 1, goods + 1 + n);
bag(goods, M, n);
return 0;
}模擬退火
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
void knapsackSa(int w[], int c[], int n, int M) { //n件物品，其重量和價(jià)值分別為w[i]和c[i]，尋找將其裝入容量為M的背包中物品的最大價(jià)值
int i, j, df, dm;
int *x = new int[n]; //定義解空間
for (i = 0; i < n; i++) { //初始化解為0
x[i] = 0;
}
int f = 0, m = 0;
for (i = 0; i < n; i++) {
f = f + c[i] * x[i]; //初始化總價(jià)值
m = m + w[i] * x[i]; //初始化總重量
}
float t0 = 500; //控制參數(shù)t的初值
float t = t0;
float a = 0.95f; //衰減函數(shù)的系數(shù)
float e = 0.00001f;
int L = 100 * n; // Mapkob 鏈長(zhǎng)
while (t > e) { //停止準(zhǔn)則
srand((unsigned)time(NULL));//初始化隨機(jī)函數(shù)種子，srand((unsigned)time(NULL));是拿系統(tǒng)時(shí)間作為種子，由于時(shí)間是變化的，種子變化，可以產(chǎn)生不相同的隨機(jī)數(shù)。
for (int k = 0; k < L; k++) {
i = rand() % n; //隨機(jī)選取第i件物品
if (x[i] == 0) { //若i不在背包中
if (m + w[i] <= M) { //且加入總重量后不超過(guò)容量M,則直接放入背包中
x[i] = 1;
f = f + c[i];
m = m + w[i];
} else {
j = rand() % n; //隨機(jī)取出物品j
while (x[j] == 0) {
j = rand() % n; //直到x[j]為1
}
df = c[i] - c[j];
dm = w[i] - w[j];
if (m + dm <= M) //加入總重量后不超過(guò)容量M
if (df > 0 || (exp(df / t) > (double)(rand() / (double)RAND_MAX))) { //價(jià)值差大于0或以exp(df/T)的接受概率接受新解
x[i] = 1;
x[j] = 0;
f = f + df;
m = m + dm;
}
}
} else {
j = rand() % n;
while (x[j] == 1) {
j = rand() % n;
}
df = c[j] - c[i];
dm = w[j] - w[i];
if (m + dm <= M)
if (df > 0 || (exp(df / t) > (double)(rand() / (double)RAND_MAX))) { //價(jià)值差大于0或以exp(df/T)的接受概率接受新解
x[i] = 0;
x[j] = 1;
f = f + df;
m = m + dm;
}
}
}
t = t * a; //衰減函數(shù)
}
cout << "該0/1背包問(wèn)題的最優(yōu)解為： ";
for (i = 0; i <= n - 1; i++) cout << x[i] << " ";
cout << endl << "最大總價(jià)值為：" << f << endl;
}
int main() {
int n, M;
//n件物品，其重量和價(jià)值分別為w[i]和c[i]，尋找將其裝入容量為M的背包中物品的最大價(jià)值
cout << "請(qǐng)輸入物品件數(shù)n:" << endl;
cin >> n;
cout << "請(qǐng)輸入背包容量M:" << endl;
cin >> M;
int *w = new int[n];
cout << "請(qǐng)依次輸入物品重量和價(jià)值:" << endl;
int *c = new int[n];
for (int i = 0; i < n; i++) {
cin >> w[i] >> c[i];
}
knapsackSa(w, c, n, M);
return 0;
}測(cè)試用例文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-784892.html
8 8
2 5
3 8
2 6
4 9
5 10
4 7
3 8
5 14
到了這里，關(guān)于湘潭大學(xué) 算法設(shè)計(jì)與分析實(shí)驗(yàn) 回溯 動(dòng)態(tài)規(guī)劃 貪心 模擬退火解決背包問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
