用C ++在0/1背包中打印项目
给定n个项目的权重和值；任务是按照容量为W的背包的以下重量和值，按0/1背包打印物品，以在背包中获得最大的总值。
什么是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作为最大利润时，我们将回溯该表以进行查找。当我们添加第二项时，我们得到了它
因此，我们将在背包中添加第二和第四项，以有效地填充袋子并实现最大利润。
示例
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; }
//的背包中的物品
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
//自底向上构建表K[][]
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];
}
}
//存储背包的结果
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];
}
}
}
//主要代码
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