資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的 0/1 揹包問題列印物品
給定 n 個物品的重量和價值；任務是根據 0/1 揹包問題，對於以下物品的重量和價值，打印出放入容量為 W 的揹包中的物品，以獲得揹包中的最大總價值。
什麼是 0/1 揹包問題？
揹包就像一個尺寸固定或能承受一定重量的袋子。每個放入揹包的物品都有其價值（利潤）和重量。我們需要選擇那些能夠在揹包所能承受的總重量範圍內，為我們帶來最大利潤的物品。
所以我們有物品的重量、價值（利潤）以及揹包所能承受的總重量。在 0/1 揹包問題中，我們只需用 1 和 0 來表示物品是否被放入揹包，其中 0 表示該物品不能放入揹包，而 1 表示該物品可以放入揹包。
讓我們透過一個簡單的例子來理解：
Let us assume val[] = {1, 2, 5, 6}//value or profit
wt[] = {2, 3, 4, 5}//weight
W = 8//Capacity其揹包表如下：
knapsack.jpg
可以使用以下公式填充揹包表：
K [i ,w] = max {K [i−1, w], K [i−1, w−wt [i]] + Val[i]}
使用回溯法求解表格，
現在我們有了每個物品的資料，包括它們的利潤以及在最大重量限制下，新增某些物品後所能獲得的最大利潤。
- 從 k[n][w] 開始回溯，其中 k[n][w] 為 8。
- 我們將向上回溯，就像藍色箭頭引導我們一直向上，而黑色箭頭指向的方向。因此，8 僅在第 4 行，所以我們將包含第 4 個物品，這意味著在新增第 4 個物品後我們獲得了最大利潤。
- 我們將總利潤 8 減去新增第 4 個物品獲得的利潤 6，得到 2。
- 我們將回溯表格，查詢何時獲得最大利潤 2。當我們新增第 2 個物品時，我們得到了 2。
- 所以我們將第 2 個和第 4 個物品放入揹包中，以有效地填充揹包並獲得最大利潤。
示例
Input: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
Output: 220 //max value
30 20 //weights
Explanation: to reach till the maximum weight i.e. 50 we will add two weights value,
30 whose value is 120 and 20 whose value is 100
Input: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
Output: 50
4 2
Explanation: to reach till the maximum weight i.e. 6 we will add two weights value, 4
whose value is 40 and 2 whose value is 10.演算法
Start
Step 1-> In function max(int a, int b)
Return (a > b) ? a : b
Step 2-> In function printknapSack(int W, int wt[], int val[], int n)
Decalare i, w, K[n + 1][W + 1]
Loop For i = 0 and i <= n and i++
Loop For w = 0 and w <= W and w++
If i == 0 || w == 0 then,
Set K[i][w] = 0
Else If wt[i - 1] <= w then,
Set K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
Else
Set K[i][w] = K[i - 1][w]
Set res = K[n][W]
Print res
Set w = W
Loop For i = n and i > 0 && res > 0 and i--
If res == K[i - 1][w] then,
Continue
Else {
Print wt[i - 1])
Set res = res - val[i - 1]
Set w = w - wt[i - 1]
Step 3-> In function int main()
Set val[] = { 50, 120, 70 }
Set wt[] = { 10, 20, 30 }
Set W = 50
Set n = sizeof(val) / sizeof(val[0])
Call function printknapSack(W, wt, val, n)
Stop示例
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
// stores the result of Knapsack
int res = K[n][W];
printf("maximum value=%d\n", res);
w = W;
printf("weights included\n");
for (i = n; i > 0 && res > 0; i--) {
if (res == K[i - 1][w])
continue;
else {
printf("%d ", wt[i - 1]);
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
// main code
int main() {
int val[] = { 50, 120, 70 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0;
}輸出
maximum value=190 weights included 30 20
更新於: 2019-12-23
1K+ 閱讀量
廣告