0/1背包问题 - 动态规划（C++实现）

flyfish

以下代码在VC++2013下编译通过

#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

int f[n+1][C+1];
std::vector<Item> allItems;//所有的物品
std::vector<Item> selectedItems;//装入背包的物品
int maxValue=0;//能够装入背包的最大价值


void Result()
{

int currentWeight = C;
for (int i = n; i > 0 && currentWeight > 0; i--) {
if (f[i][currentWeight] == f[i - 1][currentWeight - allItems[i].weight] + allItems[i].value){
            selectedItems.push_back(allItems[i]);
            currentWeight -= allItems[i].weight;
        }
    }
}
void KnapsackProblem_DynamicProgramming() {

for (int i = 1; i <= n; i++) {
for (int j = 0; j < allItems[i].weight; j++)
            f[i][j] = f[i - 1][j];
for (int j = allItems[i].weight; j <= C; j++)
            f[i][j] = std::max(f[i - 1][j], f[i - 1][j - allItems[i].weight] + allItems[i].value);
    }
    maxValue = f[n][C];
    Result();

}
int _tmain(int argc, _TCHAR* argv[])
{

memset(f, 0, sizeof(f));
        allItems.push_back(Item(0, 0, 0));
        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_DynamicProgramming();


for (size_t i = 0; i < selectedItems.size(); i++)
std::cout << "物品编号：" << selectedItems[i].id 
            << " 重量：" << selectedItems[i].weight
            << " 价值：" << selectedItems[i].value << std::endl;

std::cout << "背包最大价值：" << maxValue;
return 0;
}