[动态规划]完全背包问题及其优化

2023-12-24 13:30:27

题目描述

有N种物品和一个容量为?V?的背包,每种物品都有无限件可用。

第?i?种物品的体积是Ci,价值是Wi。求解在不超过背包容量的情况下,能够获得的最大价值。

54E9C51263E1462585A8F6595841EEC0.jpg


输入

第一行为两个整数N、V(1≤N,V≤10000),分别代表题目描述中的物品种类数量N和背包容量V。

后跟N行,第?i?行两个整数Ci、Vi,分别代表每种物品的体积和价值。

输出

输出一个整数,代表可获得的最大价值。


样例输入

5 20
2 3
3 4
10 9
5 2
11 11
样例输出
30

数据规模与约定

时间限制:1s

内存限制:64M

对于100%的数据,1≤N,V≤10000。

解题分析1

还是先上二维dp数组的做法。dp[i][j]代表前i个物品,背包容量为j的情况下能得到的最大价值。首先,我们可以采用容斥原理,对于第i个物品,如果我们不取它,那么我们的dp[i][j]=dp[i-1][j],这点没有问题,如果我们取它,dp[i][j]=dp[i][j-w[i]]+v[i],其中w[i]代表这个物品的重量,v[i]代表这个物品的价值,为什么我们又是考虑i呢?因为物品的数量是无限的,我们可以继续考虑这个物品。

代码实现1
#include <iostream>
#define MAXN 10005
using namespace std;

int N,V,C[MAXN],v[MAXN],dp[MAXN][MAXN];

int main(){
	scanf("%d%d",&N,&V);
	for(int i=1;i<=N;i++){
		scanf("%d%d",&C[i],&v[i]);
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=V;j++){
			dp[i][j]=dp[i-1][j];
			if(C[i]<=j) 
			dp[i][j]=max(dp[i][j],dp[i][j-C[i]]+v[i]);
		}
	printf("%d\n",dp[N][V]);
	return 0;
}

稍稍优化一下内存

#include <iostream>
#define MAXN 10005
using namespace std;

int N,V,C[MAXN],v[MAXN],dp[2][MAXN];

int main(){
	scanf("%d%d",&N,&V);
	for(int i=1;i<=N;i++){
		scanf("%d%d",&C[i],&v[i]);
	}
	for(int i=1,ind,rind;i<=N;i++){
		ind=i%2,rind=(i-1)%2;
		for(int j=1;j<=V;j++){
			dp[ind][j]=dp[rind][j];
			if(C[i]<=j) 
			dp[ind][j]=max(dp[ind][j],dp[ind][j-C[i]]+v[i]);
		}
	}
	printf("%d\n",dp[N%2][V]);
	return 0;
}

优化一下时间

#include <iostream>
#define MAXN 10005
using namespace std;

int N,V,dp[2][MAXN];

int main(){
	scanf("%d%d",&N,&V);
	for(int i=1,ind,rind,c,v;i<=N;i++){
		ind=i%2,rind=(i-1)%2;
		scanf("%d%d",&c,&v);
		for(int j=1;j<=V;j++){
			dp[ind][j]=dp[rind][j];
			if(c<=j) 
			dp[ind][j]=max(dp[ind][j],dp[ind][j-c]+v);
		}
	}
	printf("%d\n",dp[N%2][V]);
	return 0;
}

终极优化,注意,这里必须从正向开始打表,因为我们在状态转移的时候考虑的dp[i][j-c]+v必须是更新过后的,这是和0,1背包最大的区别。

#include <iostream>
#define MAXN 10005
using namespace std;

int N,V,dp[MAXN];

int main(){
	scanf("%d%d",&N,&V);
	for(int i=1,c,v;i<=N;i++){
		scanf("%d%d",&c,&v);
		for(int j=c;j<=V;j++){
			dp[j]=max(dp[j],dp[j-c]+v);
		}
	}
	printf("%d\n",dp[V]);
	return 0;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135180532
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。