首页 > 其他分享 >完全背包问题

完全背包问题

时间:2022-12-07 17:24:17浏览次数:60  
标签:方程 背包 int max 完全 问题 物品 include

题目链接:https://www.acwing.com/problem/content/3/

题目描述

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入描述

第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。

输出描述

输出一个整数,表示最大价值。
0<N,V≤1000
0<vi,wi≤1000

示例

输入

4 5
1 2
2 4
3 4
4 5

输出

10

分析

约定

我们记第i件物品的体积和价值为v[i],w[i]

状态表示

f(i,j)表示满足如下条件的方案的最大价值:

  • 仅从前i件物品中选择
  • 所选取的物品体积小于等于j

状态划分

对于f(i,j),存在两大种情况:

  • 没选第i件物品
  • 选了第i件物品,要考虑选了几件,1、2、3直到上限都应该考虑

状态转移方程

对应状态划分,我们便可以得到相应的状态转移方程:

  • f(i,j)=f(i-1,j)
  • f(i,j)=max(f[i-1][j-k*v[i]]+k*w[i])   (k*v[i]<=j,k=1,2,3----)

注意,第二行方程中的第一维为i-1,因为该种大情况将选了几件第i件物品剥离开再求和处理的。

显然,我们要取的f(i,j)应当是两大种情况的最大值,将二者形式统一,最终的状态转移方程如下:
f(i,j)=max(f(i-1,j-k*v[i])+k*w[i])   (k*v[i]<=j,k=0,1,2,3----)

优化

此时,通过状态转移方程进行编程实现需要三层循环,时间复杂度高,我们需要改进状态转移方程,以对代码做出优化。
我们可以注意到:

  • f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],f(i-1,j-3*v[i])+3*w[i],---)
  • f(i,j-v[i])=max(f(i-1,j-v[i]),f(i-1,j-2*v[i])+w[i],f(i-1,j-3*v[i])+2*w[i],---)

显然,我们在计算f(i,j)时可以利用f(i,j-v[i]),得到新的状态转移方程如下:
f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i])   (j-v[i]>=0)
利用该方程,我们只需要两层循环便能解决问题,时间复杂度降低。

再优化

类比0-1背包问题优化的思路:

以上,是以f(i,j)这样一个二维的函数来求解本问题的思路,我们可以想象出一张二维的表格,行对应i,列对应j,求解的过程其实就是一行一行填表的过程,不断利用之前求出的结果,最终得到最终答案。

此时我们依然可以这样考虑,对于一个f(i,j),在表中我们仅需要它正上方的元素和它左边的元素,因此采用滚动数组的思想,将原数组改为一维,减少空间开销,略微加快时间。
另外需要注意第二层循环的顺序:0-1背包问题,需要的正上方和左上方的数据,从后往前循环才不会覆盖计算新行需要的数据,但是本问题中需要的是正上方和左边的数据,必须从前往后循环。

朴素解法AC代码


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;
int n, V;
int v[N], w[N];
int f[N][N];

int main()
{
	cin >> n >> V;

	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			for (int k = 0; k * v[i] <= j; k++)
			{
				f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
			}
		}
	}

	cout << f[n][V] << endl;
	return 0;
}

时间优化AC代码


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;
int n, V;
int v[N], w[N];
int f[N][N];

int main()
{
	cin >> n >> V;

	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];

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

	cout << f[n][V] << endl;
	return 0;
}

时间空间优化AC代码


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;
int n, V;
int v[N], w[N];
int f[N];

int main()
{
	cin >> n >> V;

	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];

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

	cout << f[V] << endl;
	return 0;
}

标签:方程,背包,int,max,完全,问题,物品,include
From: https://www.cnblogs.com/kongaobo/p/16963682.html

相关文章

  • 多重背包问题
    题目链接:https://www.acwing.com/problem/content/5/题目描述有N种物品和一个容量是V的背包。第i种物品最多有si件,每件体积是vi,价值是wi。求解将哪些物品装......
  • 安全漏洞修复-常见问题及解决方案汇总
    1.跨站点请求伪造在项目进行安全测试时,通过AppScan进行漏洞扫描,出现一下问题:  也就是说请求头中缺失"Referer"或未验证Referer的值。由于是前后端分离的项目,前端使用......
  • 0-1背包问题
    题目链接:https://www.acwing.com/problem/content/description/2/题目描述有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是vi,价值是w......
  • Feign远程调用的问题
    1.Feign远程调用丢失请求头问题问题:使用feign远程调用会创建一个新request,会丢失请求头。解决:加上feign远程调用的请求拦截器。使用拦截器apply方法应用拦截器,使用Request......
  • jquery form表单.serialize()序列化后中文乱码问题原因及解决
    有时候我们需要使用ajax提交去提交form的值,这样就需要使用serialize()去获取form的值,但这样获取的值如果有中文,会乱码,原因和解决方法如下:原因:.serialize()自动调用了encodeU......
  • yolov3/4 转换为caffemodel 并且验证检测图片功能 简单记录遇到的一个问题
    过程需要设计github上的caffe、darknet2caffe、caffe-yolov3等资源,具体编译安装过程可以参考网络上的其他资源。注意这个过程有一个很关键的地方,就是caffe-yolov3的实现是......
  • MySQL8.0的caching_sha2_password问题
    问题描述及分析安装MySQL8.0后,使用MySQLWorkbench登录时报以下错误分析及查找相关资料后,发现MySQL8.0采用了新的更安全的验证方式,详情请查看​​mysql-8-0-4-new-default-......
  • POM net.sf.json-lib:json-lib报错问题解决
    在配置项目的Jackson的时候,需要添加依赖<dependency><groupId>net.sf.json-lib</groupId><artifactId>json-lib</artifactId><......
  • /dev/mapper/centos-root 100%问题
     一直没注意系统运行情况,可能最近实验攒了太多缓存。1、使用此命令可确认大文件: cd/&&du-sh *2、使用此命令确认大的目录:cd/&&du-h-x--max-depth=13、经......
  • 动态SQL遇到的问题
    看图    查不出来任何数据因为判断有问题修改方法如下: ......