# 动态规划

M[i,j] = max { M[i-1,j], M[i-1,j-si]+vi }. 如果我们把他放在二维数组里面的话，可以看出来这里的M[i,j]取决与上一层的M[i-1]中的2个元素。

M(j) = max { M(j-1), max {M(j-si)+vi, si

view plaincopy to clipboardprint?
// Knapsack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
//Unbounded knapsack problem
struct Item
{
int w;
int p;
};
/**
* Description: Calulate the max profit of unbounded knapsack problem
*@param b, item vector
*@param c, knapsack capacity
*@return the max profit
*/
int unbounded_knapsack( const std::vector & b, unsigned int c )
{
std::vector m (c+1);
std::vector p (c+1); // use to backtrack the item chosen
for (int j=1;j<=c;j++)
{
int max = 0;
for (int i=0;i        {
if ( j-b[i].w >=0)
{
if ( max < m[j-b[i].w] + b[i].p )
{
max = m[j-b[i].w] + b[i].p;
p[j] = j-b[i].w;
}
}
}
m[j] = std::max(max, m[j-1]);
if ( max < m[j-1] )
{
p[j] = p[j-1];
}
m[j] = max;
}
return m[c];
}
/**
* Description: Calulate the max profit of 0-1 knapsack problem
*@param b, item vector
*@param c, knapsack capacity
*@return the max profit
*/
int zero_one_knapsack( const std::vector & b, unsigned int c )
{

if (b.size() < 1) return 0;
std::vector< std::vector > m ( b.size()+1, std::vector(c+1) );

for (int i=1;i<=b.size();i++)
{
for (int j=1;j<=c;j++)
{
if ( j-b[i-1].w >=0 )
m[i][j] = std::max<>( m[i-1][j], m[i-1][j-b[i-1].w]+b[i-1].p );
else
m[i][j] = m[i-1][j];
}
}
return m[b.size()][c];
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector b(5);
b[0].w = 3;
b[0].p = 4;
b[1].w = 4;
b[1].p = 5;
b[2].w = 7;
b[2].p = 10;
b[3].w = 8;
b[3].p = 11;
b[4].w = 9;
b[4].p = 13;
int c = 17;
std::cout<    std::cout<    system("pause");
return 0;

// Knapsack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
//Unbounded knapsack problem
struct Item
{
int w;
int p;
};
/**
* Description: Calulate the max profit of unbounded knapsack problem
*@param b, item vector
*@param c, knapsack capacity
*@return the max profit
*/
int unbounded_knapsack( const std::vector & b, unsigned int c )
{
std::vector m (c+1);
std::vector p (c+1); // use to backtrack the item chosen
for (int j=1;j<=c;j++)
{
int max = 0;
for (int i=0;i  {
if ( j-b[i].w >=0)
{
if ( max < m[j-b[i].w] + b[i].p )
{
max = m[j-b[i].w] + b[i].p;
p[j] = j-b[i].w;
}
}
}
m[j] = std::max(max, m[j-1]);
if ( max < m[j-1] )
{
p[j] = p[j-1];
}
m[j] = max;
}
return m[c];
}
/**
* Description: Calulate the max profit of 0-1 knapsack problem
*@param b, item vector
*@param c, knapsack capacity
*@return the max profit
*/
int zero_one_knapsack( const std::vector & b, unsigned int c )
{

if (b.size() < 1) return 0;
std::vector< std::vector > m ( b.size()+1, std::vector(c+1) );

for (int i=1;i<=b.size();i++)
{
for (int j=1;j<=c;j++)
{
if ( j-b[i-1].w >=0 )
m[i][j] = std::max<>( m[i-1][j], m[i-1][j-b[i-1].w]+b[i-1].p );
else
m[i][j] = m[i-1][j];
}
}
return m[b.size()][c];
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector b(5);
b[0].w = 3;
b[0].p = 4;
b[1].w = 4;
b[1].p = 5;
b[2].w = 7;
b[2].p = 10;
b[3].w = 8;
b[3].p = 11;
b[4].w = 9;
b[4].p = 13;
int c = 17;
std::cout< std::cout< system("pause");
return 0;
}

1. Subset Sum Problem. Partition Problem. 这是两个类似的问题。Subset Sum Problem被称为子集和问题。题目的意思是给定一个集合，判断是否存在和等于某特定值s的子集。 Partition Problem的中文名字我不知道:)但是题目的意思是一个给定的集合A，把他分成A1和A2两个子集。使得两个子集合的差|A1-A2|尽量小。第二个问题其实可以转化成第一个问题。可以找到全集A的合1/2。然后找到和A/2最接近的子集就可以了。这样的问题和01背包还是很类似的。我们依然定义一个M[i,j]这里的意义有些不一样,M[i,j]表示能否用第1...i-1个整数找到和为j的方案。如果可以就是1，不能就为0。那样这个M[i,j]可以表示为：M[i,j] = M[i-1,j] || M[i-1,j-Ai] 也就是说对于第i个整数来说，要么存在不用这个整数的方案M[i-1,j]或者存在方案M[i-i,j-Ai],这第二个方案加上了当年Ai也就可以了。有兴趣的话可以实现一下。

2. change-making Problem.这个问题通俗的描述就是你去超市买东西，最后的零钱是75分。你肯定不希望营业员给你75一个1分的硬币，营业员需要做的事情就是计算出一个给你最少个数硬币的方案。如果我们假定特定的硬币营业员都有的话，我们可以把这个问题看成近似的完全背包问题。不过完全背包问题的要求是满足重量的价值尽量大。这里在于满足条件的硬币数量尽可能小。一样的我们定义一个和完全背包类似的M[j]来表示找零钱j需要的硬币数量。那么M[j] = min { M[j-Ai] + 1, 1<=i<=n }这个j取决于比之小的所有M[j-Ai]的最优硬币数量方案的最小值。除了这里的max换乘了min。其他的都非常像吧。

其实类似的问题还是有很多，这里先贴一些出来总结，如果有更好的例子。以后在补充上去，但是现在这种工作的方式让人真的很舒服^_^

• 博文量
51
• 访问量
117098