1.問題描述
有n個(gè)物體有重量和價(jià)值兩個(gè)屬性猎拨，一個(gè)能承重一定重量的背包。問怎么選擇物體能實(shí)現(xiàn)背包里的價(jià)值最大化。
2.問題具體化
假設(shè)有5個(gè)物體和一個(gè)背包鹤盒。物體的重量分別是2百炬、2褐隆、6、5剖踊、4庶弃，即w[]={0、2德澈、2歇攻、6、5梆造、4}缴守，價(jià)值分別是6、3、5屡穗、4贴捡、6，即v[]={0村砂、6烂斋、3、5础废、4汛骂、6}。背包承重為10评腺。問怎么選擇香缺，能實(shí)現(xiàn)背包所背物體價(jià)值的最大化。
3. 解決過程
利用二維表格歇僧，通過自左向右图张、自下向上的計(jì)算，來繪制表格诈悍，左后再在表格的基礎(chǔ)上選擇最優(yōu)解祸轮。
- 3.1表格最后一行
對(duì)最后一行的物體4來說，只有兩種情況侥钳，要么裝入背包适袜，要么不裝入。物體5的的重量是4舷夺。也就是說在背包承重為0--3的時(shí)候物體5是裝不進(jìn)去的苦酱，所以背包為0，當(dāng)背包承重為4--10的時(shí)候给猾，物體5可以裝進(jìn)去疫萤，又因?yàn)槲矬w5的價(jià)值為6，所以背包價(jià)值為6敢伸。
|.|0|1|2|3|4|5|6|7|8|9|10|
|--
|1
|2
|3
|4|
|5|0|0|0|0|6|6|6|6|6|6|6|
-
3.2表格倒數(shù)第二行
表格倒數(shù)第二行的計(jì)算思路與倒數(shù)第一不一樣扯饶，因?yàn)槲覀円紤]背包里已經(jīng)有的物體。因?yàn)槲矬w4的重量為5池颈。所以在背包承重為0--4的情況下即使空包也裝不進(jìn)去尾序，所以不能裝入，包里原本是多少價(jià)值躯砰，就還是多少價(jià)值每币。在背包承重為5--8的時(shí)候，物體4可以裝進(jìn)去琢歇，但是物體5要拿出來才行兰怠，這樣的話背包的價(jià)值就變成4了梦鉴，小于6。所以能然選擇不把物體4放進(jìn)去痕慢。在背包承重為9--10的時(shí)候尚揣，兩個(gè)都可以放進(jìn)去，所以背包的價(jià)值變成10了掖举。
|.|0|1|2|3|4|5|6|7|8|9|10|
|--
|1
|2
|3
|4|0|0|0|0|6|6|6|6|6|10|10|
|5|0|0|0|0|6|6|6|6|6|6|6|
- 3.3最終計(jì)算出來的表格
其他行的計(jì)算過程同上快骗，最終結(jié)果如下。
|.|0|1|2|3|4|5|6|7|8|9|10|
|--
|1|0|0|6|6|9|9|12|12|15|15|15|
|2|0|0|3|3|6|6|9|9|9|10|11|
|3|0|0|0|0|6|6|6|6|6|10|11|
|4|0|0|0|0|6|6|6|6|6|10|10|
|5|0|0|0|0|6|6|6|6|6|6|6|
- 3.4表格計(jì)算公式
max( m(i+1,j) , m(i+1,j-wi)+vi )
- 3.5做出最優(yōu)選擇
大體思想：我們從右上角（坐標(biāo)（1,10））開始塔次，看（1,10）與（2,10）的值是不是一樣方篮，一樣，則說明物體1沒裝進(jìn)去励负，不一樣藕溅，則說明物體1裝進(jìn)去了。
void opt_way(int flag[],int w[], int table[num][weight])
{
int n = weight-1;
for (size_t i = 0; i < num; i++)
{
if (table[i][n]==table[i+1][n])
{
flag[i] = 0;
}
else
{
flag[i] = 1;
n = n - w[i+1];
}
}
}
4.完整代碼
#include <iostream>
#define num 5
#define weight 11
using namespace std;
void init_table(int table[num][weight])
{
for (size_t i = 0; i < num; i++)
{
for (size_t j = 0; j < weight; j++)
{
table[i][j] = 0;
}
}
}
void show_table(int table[num][weight])
{
for (size_t i = 0; i < num; i++)
{
for (size_t j = 0; j < weight; j++)
{
cout <<table[i][j] << "\t";
}
cout << "\n";
}
}
void creat_table(int table[num][weight],int w[],int v[])
{
//給最后一行賦初值
for (size_t i = 0; i < weight; i++)
{
if (w[num] > i)
table[num - 1][i] = 0;
else
{
table[num - 1][i] = v[num];
}
}
//在最后一行基礎(chǔ)上給每行賦值
for (int i = num - 1; i > 0; i--)
{
for (int j = 0; j < weight; j++)
{
if (w[i]>j)
{
table[i - 1][j] = table[i][j];
}
else if ((v[i] + table[i][j-w[i]])>table[i][j])
{
table[i-1][j] = v[i] + table[i ][j - w[i]];
}
else
{
table[i-1][j] = table[i][j];
}
}
}
}
void opt_way(int flag[],int w[], int table[num][weight])
{
int n = weight-1;
for (size_t i = 0; i < num; i++)
{
if (table[i][n]==table[i+1][n])
{
flag[i] = 0;
}
else
{
flag[i] = 1;
n = n - w[i+1];
}
}
}
int main()
{
int w[num+1] = {0,2,2,6,5,4};
int v[num+1]= {0,6,3,5,4,6};
int flag[num] = { 0, 0, 0, 0, 0 };
int table[num][weight];
init_table(table);
creat_table(table,w,v);
opt_way(flag,w,table);
//----------------
show_table(table);
//------------------------------
for (size_t i = 0; i < num; i++)
{
cout << flag[i];
}
getchar();
return 0;
}
5.程序結(jié)果截圖
