用P1060来讲解01背包

P1060 开心的金明（基础背包）

这道题是01背包裸题

超级难

首先讲解一下01背包

01背包的基本模型为 已经拥有的资本（即背包容量）

可以获得物品的价值和代价（即物品的价值和体积）

所以我们用最基本的无任何优化的代码实现一下

for(int i=1;i<=m;i++)//枚举所有物品 一共m个物品 所以从1到m
{
	for(int j=0;j<=n;j++)//此处为枚举背包容量  即背包满容量为n
	{
		if(j<v[i])//如果当前容量小于当前物品的体积 便无法放下 所以 dp[i][j]状态和dp[i-1][j]一致
			dp[i][j]=dp[i-1][j];//dp[i][j]代表当前放前i个物品剩余容量为j时的价值
		else
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//状态转移方程
	}
}

　　

可以来用knapsack来模拟样例中的过程（一个01背包小插件）地址为http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html

继续加油~

爱老婆.jpg

4月8日下午更新！

突然学会了用一维数组优化01背包

能够降低空间复杂度！

 放上代码和自身理解

for(int i=1;i<=n;i++)//dp[i]代表重量不超过i的背包的最大可获取价值
{
    for(int j=m;j>=w[i];j--)//这里dp[]一定要逆序   原因为无优化下 像一个表格 每次使用上一行的数据进行比较 如dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);所以 每次使用为上组数据
    {
        dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
    }
}

 突然又听说常数可以优化掉？？？

在网上找到了代码 可惜 看不懂 等着补博客吧