C++ 0/1背包问题

背包容量=8.求背包所能装物品的最大价值及物品的编码。

思路：动态规划，在每个阶段的决策中，始终保持当前所完成的决策使得背包的价值是最大的。

dp[i][j]:表示前i个物品能放入背包的价值为j。

// 背包或购物单.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include 
#include 
#include 
using namespace std;
void find(int i, int j);
int object[5] = { 0 };
int weight[5] = { 0, 2, 3, 4, 5 };
int value[5] = { 0, 3, 4, 5, 6 };
vector>dp(5, vector(9, 0));

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

	//前i个物品在容量为j的情况下，最大的价值
	for (int i = 1; i < 5; i++)//i表示物品的编号
	{
		for (int j = 1; j < 9; j++)//j表示背包的容量
		{
			if (weight[i] > j)//当前物品的体积大于背包容量
			{
				dp[i][j] = dp[i - 1][j];//当前物品不放，其价值等于放前i-1个物品
			}
			else//放第i个物品，找最大。保证有放第i个物品的空间即j-weight[i],价值dp[][]+value[i]
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
			}
		}
	}
	int ans = dp[4][8];
	
	//回溯求放入背包的物品编码
	cout << "装入背包的物品编号：n";
	find(4, 8);

	return 0;
}

void find(int i, int j)
{
	if (i == 0)
	{
		for (int i = 0; i < 5; i++)
		{
			if (object[i] == 1)
			{
				cout << i<< ' ';
			}
		}
		return;
	}
	if (dp[i][j] == dp[i - 1][j])
	{
		object[i] = 0;
		find(i - 1, j);
	}
	else if (dp[i][j] == dp[i - 1][j - weight[i]] + value[i])
	{
		object[i] = 1;
		find(i - 1, j - weight[i]);
	}
}