#include "stdafx.h" #include <iostream> #include <algorithm> #include <vector> struct Item //物品定义 { int id, weight, value;//编号，重量，价值。编号为0的物品这里没有使用 Item(){} Item(int i, int w, int v) :id(i), weight(w), value(v){} }; const int n=4, C=10; //C背包所能承受的最大重量 //物品个数n std::vector<Item> allItems;//所有的物品 std::vector<Item> selectedItems;//装入背包的物品 int maxValue=0;//能够装入背包的最大价值 void Result(int solution) { selectedItems.clear(); for (int i = 0; i < n ; i++) { if (solution & 1) selectedItems.push_back(allItems[i]); solution >>= 1; } } int KnapsackProblem_BruteForce() { int allCase = static_cast<int>(std::pow(2, n)); maxValue = 0; for (int i = 0; i < allCase; i++) { int currentCase = i, currentWeight = 0, currentValue = 0; for (int j = 0; j < n ; j++) //将所有二进制是1,所代表物品的重量和价值各自计算累加和 { if (currentCase & 1)// //二进制位等于1，则物体放进背包，0不放 { currentWeight += allItems[j].weight; currentValue += allItems[j].value; } if (currentWeight > C)//如果已经超重了就不需要继续加了 break; currentCase = currentCase >>1; //计算完移除一个 } if (currentWeight <= C && currentValue > maxValue) { maxValue = currentValue; Result(i); } } return maxValue; } int _tmain(int argc, _TCHAR* argv[]) { allItems.push_back(Item(1, 3, 30)); allItems.push_back(Item(2, 5, 20)); allItems.push_back(Item(3, 4, 10)); allItems.push_back(Item(4, 2, 40)); KnapsackProblem_BruteForce(); std::cout<< maxValue; return 0; }