背包问题入门 模板 博客

背包问题入门 模板 博客

https://blog.csdn.net/yandaoqiusheng/article/details/84782655 背包问题九讲个人整理, 很好。

https://blog.csdn.net/qq_33997572/article/details/79216132 hdu 1059 多重背包 代码实现

一些小的注意点

1. 要求背包正好装满

   这里按照一般的做法是dp数组全部赋值为负无穷，然后dp[0]=0，然后就和普通的背包过程一样了。就想下面一样。

   for(int i=1; i<=n; i++)
   	for(int j=V; j>=w[i]; j--)
   		f[j]=max(f[j], f[j-w[i]] + v[i]);
   

   这里如果再加一步处理的话会更好，如下：

   for(int i=1; i<=n; i++)
   	for(int j=V; j>=w[i]; j--)
           if(dp[j-w[i]] > -inf)//这样每一次的转换都是从前面有效的状态转一过来
   			f[j]=max(f[j], f[j-w[i]] + v[i]);
   

2. 如果物品的重量有是负数的话

   poj 2184就是数据中有负数。

   解决方法是使得背包的向右扩展。这里参考这个题的题解，点我

//01背包
for(int i=1; i<=n; i++)
{
	for(int j=V; j>=w[i]; j--)
	{
		f[j]=max(f[j], f[j-w[i]] + v[i]);
	}
 }
 
//完全背包问题
for(int i=1; i<=n; i++)
{
	for(int j=w[i]; j<=V; j++)
	{
		f[j]=max(f[j], f[j-w[i]]+v[i]);
	}
 } 
 
//多重背包
for(int i=1; i<=n; i++)
{
	int min_num=min(num[i], V/w[i]);
	for(int k=1; min_num>0; k<<=1)
	{
		if(k>min_num)
			k=min_num;
		min_num-=k;
		for(int j=V; j>=w[i]*k; j--)
		{
			f[j]=max(f[j], f[j-w[i]*k]+v[i]*k);
		}
	}
}