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

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

×

选择打赏方式：

微信 QQ钱包 支付宝

打赏

打赏

打赏

多少都是心意！谢谢大家！！！