給定一組有固定價(jià)值和固定重量的物品，以及一個(gè)已知最大承重量的背包，求在不超過(guò)背包最大承重量的前提下，能放進(jìn)背包里面的物品的最大總價(jià)值。
這一類(lèi)問(wèn)題是典型的使用動(dòng)態(tài)規(guī)劃解決的問(wèn)題，我們可以把背包問(wèn)題分成3種不同的子問(wèn)題：0-1背包問(wèn)題、完全背包和多重背包問(wèn)題。下面對(duì)這三種問(wèn)題分別進(jìn)行討論。
1.0-1背包問(wèn)題
0-1背包問(wèn)題是指每一種物品都只有一件，可以選擇放或者不放?，F(xiàn)在假設(shè)有n件物品，背包承重為m。
對(duì)于這種問(wèn)題，我們可以采用一個(gè)二維數(shù)組去解決：f[i][j]，其中i代表加入背包的是前i件物品，j表示背包的承重，f[i][j]表示當(dāng)前狀態(tài)下能放進(jìn)背包里面的物品的最大總價(jià)值。那么，f[n][m]就是我們的最終結(jié)果了。
采用動(dòng)態(tài)規(guī)劃，必須要知道初始狀態(tài)和狀態(tài)轉(zhuǎn)移方程。初始狀態(tài)很容易就能知道，那么狀態(tài)轉(zhuǎn)移方程如何求呢？對(duì)于一件物品，我們有放進(jìn)或者不放進(jìn)背包兩種選擇：
（1）假如我們放進(jìn)背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，這里的f[i - 1][j - weight[i]] + value[i]應(yīng)該這么理解：在沒(méi)放這件物品之前的狀態(tài)值加上要放進(jìn)去這件物品的價(jià)值。而對(duì)于f[i - 1][j - weight[i]]這部分，i - 1很容易理解，關(guān)鍵是 j - weight[i]這里，我們要明白：要把這件物品放進(jìn)背包，就得在背包里面預(yù)留這一部分空間。
（2）假如我們不放進(jìn)背包，f[i][j] = f[i - 1][j]，這個(gè)很容易理解。因此，我們的狀態(tài)轉(zhuǎn)移方程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i]) 。當(dāng)然，還有一種特殊的情況，就是背包放不下當(dāng)前這一件物品，這種情況下f[i][j] = f[i - 1][j]。
#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int main() {
int n, m;
cout << "請(qǐng)輸入物品個(gè)數(shù):";
cin >> n;
cout << "請(qǐng)分別輸入" << n << "個(gè)物品的重量和價(jià)值:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
cout << "請(qǐng)輸入背包容量:";
cin >> m;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) {
f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
}
}
}
cout << "背包能放的最大價(jià)值為:" << f[m] << endl;
}
題目描述
這個(gè)表格對(duì)于理解0-1背包問(wèn)題很有用，我們利用它來(lái)理解一下為什么要把第二層循環(huán)顛倒這個(gè)問(wèn)題。考慮d9這一項(xiàng)，要求出這個(gè)狀態(tài)，我們有可能利用到的就是e1到e8這8個(gè)狀態(tài)，當(dāng)我們把第二層循環(huán)顛倒過(guò)來(lái)時(shí)，當(dāng)我們要求f[j]時(shí)，f[j -1]到f[1]還保存著下面一行的狀態(tài)，因此可以采用一維數(shù)組解決。我們可以考慮一下假如不把第二層循環(huán)顛倒，當(dāng)要求f[j]時(shí)，f[j - 1]到f[1]已經(jīng)是同一行的狀態(tài)了，根本沒(méi)法求。
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) {
f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
}
}
}
2.完全背包問(wèn)題
#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, m;
cout << "請(qǐng)輸入物品個(gè)數(shù):";
cin >> n;
cout << "請(qǐng)分別輸入" << n << "個(gè)物品的重量和價(jià)值:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
cout << "請(qǐng)輸入背包容量:";
cin >> m;
for (int i = 1; i <= n; i++) {
for (int j = weight[i]; j <= m; j++) {
f[j] = max(f[j], f[j - weight[i]] + value[i]);
}
}
cout << "背包能放的最大價(jià)值為:" << f[m] << endl;
}
完全背包問(wèn)題與0-1背包問(wèn)題的區(qū)別
1.完全背包問(wèn)題內(nèi)層循環(huán)是順序的，而0-1背包問(wèn)題是逆序的。。
0-1背包為逆序的原因是為了求max中的兩項(xiàng)是前一狀態(tài)的值。
而現(xiàn)在是要求當(dāng)前狀態(tài)的值，因?yàn)槊糠N背包都是無(wú)限的，當(dāng)我們從1到N循環(huán)時(shí)，f[v]表示容量為v在前i種背包所得的價(jià)值，這里我們添加的不是前一個(gè)背包，而且當(dāng)前背包，所以應(yīng)考慮當(dāng)前狀態(tài)。
3.多重背包問(wèn)題
多重背包問(wèn)題限定了一種物品的個(gè)數(shù)，解決多重背包問(wèn)題，只需要把它轉(zhuǎn)化為0-1背包問(wèn)題即可。比如，有2件價(jià)值為5，重量為2的同一物品，我們就可以分為物品a和物品b，a和b的價(jià)值都為5，重量都為2，但我們把它們視作不同的物品。
#include <iostream>
using namespace std;
#define V 1000
int weight[50 + 1];
int value[50 + 1];
int num[20 + 1];
int f[V + 1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, m;
cout << "請(qǐng)輸入物品個(gè)數(shù):";
cin >> n;
cout << "請(qǐng)分別輸入" << n << "個(gè)物品的重量、價(jià)值和數(shù)量:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i] >> num[i];
}
int k = n + 1;
for (int i = 1; i <= n; i++) {
while (num[i] != 1) {
weight[k] = weight[i];
value[k] = value[i];
k++;
num[i]--;
}
}
cout << "請(qǐng)輸入背包容量:";
cin >> m;
for (int i = 1; i <= k; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) f[j] = max(f[j], f[j - weight[i]] + value[i]);
}
}
cout << "背包能放的最大價(jià)值為:" << f[m] << endl;
}
