0-1背包问题
一、问题描述：给定n种物品和一个背包，物品i的重量是wi，其价值是vi，背包的容量为c。问应该如何选择装入背包中的物品，使得装入背包中的物品总价值最大。每种物品只有装入或不装入两种选择，不能装入部分也不能多次装入。
形式化描述：给定c>0，wi>0，vi>0，1<=i<=n，要求找出一个n元0-1向量(x1,x2,…,xn)，xi={0,1}，1<=i<=n，使得，而且达到最大。因此，0-1背包问题是一个特殊的整数规划问题。
二、最优子结构性质：设(y1,y2,…,yn)是所给0-1背包问题的一个最优解，则(y2,y3,…,yn)是如下子问题的一个最优解：
三、递归关系：
设所给问题的子问题：
的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值，由最优子结构性质可得到计算m(i,j)的递归式：
#include <iOStream>
using namespace std;
#define N 5 //物品个数
#define C 10 //背包容量
//价值v，重量w，背包容量c，物品个数n，背包容量为j可选择物品为[i,n]时的最优值
void Knapsack(int v[],int w[],int c,int n,int m[N][C+1])
{
for(int j=0;j<w[n-1];j++)m[n-1][j]=0; //j<wn时
for(int j=w[n-1];j<=c;j++)m[n-1][j]=v[n-1]; //j>=wn时
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<=c;j++)
{
if(j>=w[i])
{
m[i][j]=m[i+1][j];
int t=m[i+1][j-w[i]]+v[i];
if(m[i][j]<t)m[i][j]=t;
}
else m[i][j]=m[i+1][j];
}
}
}
//计算最优解x[]
void Traceback(int m[N][C+1],int w[],int c,int n,int x[])
{
for(int i=0;i<n-1;i++)
{
if(m[i][c]==m[i+1][c])x[i]=0;
else {
x[i]=1;
c-=w[i];
}
}
x[n-1]=m[n-1][c]?1:0;
}
int main()
{
int w[]={2,2,6,5,4},
v[]={6,3,5,4,6};
int m[N][C+1],x[N];
Knapsack(v,w,C,N,m);
Traceback(m,w,C,N,x);
for(int i=0;i<N;i++)
cout<<x[i]<<" ";
cout<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<=C;j++)
{
cout<<m[i][j]<<" ";
}
cout<<endl;
}
}复杂性分析：分析可得时间复杂性为O(nc)；
相关阅读
1、动态规划（DP）动态规划（Dynamic Programming，DP）与分治区别在于划分的子问题是有重叠的，解过程中对于重叠的部分只要求解一次，记录下结
以前文章讲过《基于S2b2c汽车新零售的模式解析》，本篇讲一下新零售背景下从0-1搭建B2B电商平台的方法。一. 前言一个产品从0-1搭建
以前文章讲过《基于S2b2c汽车新零售的模式解析》，本篇讲一下新零售背景下从0-1搭建B2B电商平台的方法。一. 前言一个产品从0-1搭建
问题描述 有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 为方便讲解和理解，下面
昨天做了爱奇艺的内推笔试，编程题又出现了动态规划问题，感觉动态规划出现的概率好大，需要加强下。这里借用背包问题开始我们的学习。