背包问题求最大价值（允许不装满）

背包问题主要分为01背包和完全背包

01背包就是单个物品只能使用一次

完全背包则是单个物品可以使用无限次

背包问题题目则有两大类

1：求最大价值（允许不装满）和（必须装满）

今天先看允许不装满

01背包：

01背包通用公式
d[j]=max(d[j],d[j-w[i]]+c[i]);//前提是第二个for要从v到0，这是必须的

整个过程就是
 

for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=0;j--)
		{
			if(j>=w[i])
			{
				d[j]=max(d[j],d[j-w[i]]+c[i]);
			}
		}
	}
//如果想省时间就是：
for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=w[i];j--)
		{
			d[j]=max(d[j],d[j-w[i]]+c[i]);
		}
	}

d[j]表示在总重量为j得情况下选取部分物品得最大价值

公式中的j则是背包内现有重量；

01看完了然后是完全

完全背包和01差不多公式一样
d[j]=max(d[j],d[j-w[i]]+c[i])；

不一样的是完全的顺序是从0到v；

代码如下：

for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=v;j++)
		{
			if(j>=w[i])
			{
				d[j]=max(d[j],d[j-w[i]]+c[i]);
			}
		}
	}

2：求方案总数

这个下次讲

最后

以上就是迷你河马为你收集整理的背包问题求最大价值（允许不装满）的全部内容，希望文章能够帮你解决背包问题求最大价值（允许不装满）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。