数据结构
网络
关系数据库管理系统
操作系统
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+ 阅读量
广告