0-1背包动态规划的优化过程-创新互联

1用动态规划写出0-1背包问题的解法

#include#include#includeconst int N=30;//全局变量，物品数量
const int bag=N;//全局变量，背包承重量
int max_value=0;//全局变量，记录能获得的大价值
int a[N],v[N],w[N],r[N+1];//全局变量，分别保存0-1方案，物品价值，物品重量，剩余总价值
int max(int a,int b);
int fa[N]={0};
int backpack(int i,int m)//i为第i个物品,m为有m元钱 
{
	    if(i == 0) return 0;//边界
    if(w[i]>m) 
	return  backpack(i-1,m);    //当这个物品装不下时 就不需要比较了
    else
		return max(backpack(i-1, m),backpack(i-1, m - w[i])+v[i]);
} 

int main()
{
	int i,start,end;
	printf("背包大承重%d公斤\n",bag);
	for(i=0;ib) return a;
else return b;
}

动态规划的部分主要就是这个函数

int backpack(int i,int m)//i为第i个物品,m为有m元钱 
{
	    if(i == 0) return 0;//边界
    if(w[i]>m) 
	return  backpack(i-1,m);    //当这个物品装不下时 就不需要比较了
    else
		return max(backpack(i-1, m),backpack(i-1, m - w[i])+v[i]);
}

可以看出这个代码时间复杂度是很高的，因为他有很多节点重复计算了

我们可以通过加记忆数组的方式进行优化使其算法复杂度降到O(n*N)。

#include#include#includeconst int N=1000;//全局变量，物品数量
const int bag=N;//全局变量，背包承重量
int max_value=0;//全局变量，记录能获得的大价值
int a[N],v[N],w[N],r[N+1];//全局变量，分别保存0-1方案，物品价值，物品重量，剩余总价值
int max(int a,int b);
int fa[N]={0};
int jy[1000][1000]={0};//记忆数组 
int backpack(int i,int m)//i为第i个物品,m为有m元钱 
{
	if(i == 0) return 0;//边界
	if(jy[i][m]>0)return jy[i][m]; 
    if(w[i]>m) 
		return jy[i][m]=backpack(i-1,m);//当这个物品装不下时 就不需要比较了
    else
		jy[i][m]=max(backpack(i-1,m),backpack(i-1, m - w[i])+v[i]);
	return jy[i][m];
} 

int main()
{
	int i,start,end;
	printf("背包大承重%d公斤\n",bag);
	for(i=0;ib) return a;
else return b;
}

当然，还能将其写成递推的形式

#include#include#includeconst int N=1000;//全局变量，物品数量
const int bag=N;//全局变量，背包承重量
int max_value=0;//全局变量，记录能获得的大价值
int a[N],v[N],w[N],r[N+1];//全局变量，分别保存0-1方案，物品价值，物品重量，剩余总价值
int dp[N][bag+1]={0},fa[N]={0};
int max(int a,int b);
void Find(int N,int bag);
int backpack()
{
	for(int i=1;ij)
				dp[i][j]=dp[i-1][j];
			else
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
		}
		
	}
	return dp[N-1][bag];//返回大价值
}
void Find(int i,int j)
{
	if(i==0)
	{
		for(int i=0;ib) return a;
else return b;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧