C++ 程序解决 0-1 背包问题

c++server side programmingprogramming

在 0-1 背包问题中，给定一组物品，每件物品都有重量和价值。我们需要确定要包含在集合中的每件物品的数量，以便总重量小于或等于给定的限制，并且总价值尽可能大。

输入

Value = [10, 20, 30, 40, 60, 70]
Weight=[1, 2, 3, 6, 7, 4]
int w=7

输出

knapsack value is: 100

算法

Begin
    输入:一组具有重量和价值的物品
    设置背包容量
    物品数量=sizeof(values) / sizeof(values[0])
    背包(值(存储在数组 v 中)、重量(存储在数组 w 中)、不同物品数量 (n)、背包容量 W)
    如果 (w < 0)
        返回
    如果没有剩余物品或容量变为 0
        返回 0
    将当前物品 n 包含在背包 (v[n]) 中，并递归查找剩余物品 (n - 1)，容量减少 (W - w[n])
    从背包中排除当前物品 n，并递归查找剩余物品 (n - 1)
    返回通过包含或排除当前物品获得的最大值
End

示例代码

#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
   if (W < 0)
      return INT_MIN;
   if (n < 0 || W == 0)
      return 0;
   int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
   int ex = knapSack(v, w, n - 1, W);
   return max (in, ex);
}
int main() {
   int v[] = { 10, 20, 30, 40, 60, 70 };
   int w[] = { 1, 2, 3, 6, 7, 4 };
   int W = 7;
   int n = sizeof(v) / sizeof(v[0]);
   cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
   return 0;
}