动态规划-背包问题(01,多重,完全)

发布于 2022-11-03  187 次阅读


01背包——>拿或不拿的问题。

问题:有N件体积为v,价值为w的物品。和一个体积为V的背包,求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

可以先定义一个二维数组dp[i][j]表示在第i件物品,体积为j的时候的总价值。
可以推出状态转移方程:

dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-v[i]]+w[i]

由此可知用双重循环遍历所有物品和体积,可以推出答案即dp[N][V]的值。
代码如下。

//01背包问题。
#include <iostream>
using namespace std;
int N,V;//N件物品,V为背包容量。
int v[1005],w[1005];//v为物品的体积,w为物品的价值。
int dp[1005][1005];//dp[i][j]为价值量 i为第i件物品,j为背包剩余的容量。
//!!dp[0][0-1005]为0(有可能会有测试点测0,0)
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 k=1;k<=V;k++){
			if(k<v[i])//如果第i个物品放不下。
				dp[i][k]=dp[i-1][k];//这个物品不拿。
			else
				dp[i][k]=max(dp[i-1][k],dp[i-1][k-v[i]]+w[i]);//不拿或拿。
		}
	}
	cout<<dp[N][V];//输出答案。
}

但是可以发现运用二维数组记录答案即浪费空间也浪费时间,有10000件以上物品的时候很容易超时。
所以可以把dp二维数组压缩成一维数组优化,即滚动数组优化。

打表可以发现,在递推的过程中只是用到了和上一层的数据。

如图中的数字5是通过上面的数据推出来的。

所以可以数组下标只记录背包的体积 dp[V],并通过不断的覆盖避免了记录大量无用数据的问题。(?)

(坑点)但是要注意的是,用一维数组滚动要避免可能要用的数据过早被覆盖的问题,表中正向体积V是不断增大的,小背包能装的东西大背包也一定能装,反过来就不一定了,所以要逆向去更新覆盖数组中的数据。

代码如下。

//01背包问题。
#include <iostream>
using namespace std;
int N,V;//N件物品,V为背包容量。
int v[1005],w[1005];//v为物品的体积,w为物品的价值。
int dp[1005];//dp[j]为体积为J时能装的价值量。 j为背包剩余的容量。
//!!dp[0][0-1005]为0(有可能会有测试点测0,0)
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 k=1;k<=V;k++){
			if(k<v[i])//如果第i个物品放不下。
				dp[i][k]=dp[i-1][k];//这个物品不拿。
			else
				dp[i][k]=max(dp[i-1][k],dp[i-1][k-v[i]]+w[i]);//不拿或拿。
		}
	}
	cout<<dp[N][V];//输出答案。
}

完全背包问题(每件物品都有无限件)

问题:有N种体积为v,价值为w的物品。和一个体积为V的背包,每种物品的数量是无限的,求解将怎样将物品分配入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

因为物品无限所以可以变成0/1/2/3...背包问题(?)

诶嘿,设k为取用一种物品的数量,观察原来的状态转移方程,发现可以在原来的基础上做一些小更改。
dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-v[i]]+w[i]
↓↓↓ ↓↓↓
dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-k*v[i]]+k*w[i]
再用滚动数组优化
dp[j]=max ( dp[j] , dp[j-k*v[i]]+k*w[i]

代码如下:

#include <iostream>
using namespace std;
int w[1005],v[1005],dp[1005];
int main(){
	int N,V; cin>>N>>V;//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;j>=0;k++){
			for(int k=0;k<=j/v[i];k++)
			dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);//不用判断能不能装得下了。
		}
	}
	cout<<dp[V];
	return 0;
}

但是因为用到了三重循环,所以这是非常土的方法。

可以再打个表看看。

可以发现新的数据是来自于上一行数据和新产生的数据。
在01背包的滚动数组里,新的数据是来自于上一行和上一行的旧数据得出的。
所以在完全背包可以无需给取用的物品计数,直到拿不下为止,从0开始,顺向去求解dp[V]的值。

代码如下。

#include <iostream>
using namespace std;
int w[1005],v[1005],dp[1005];
int main(){
	int N,V; cin>>N>>V;//N为物品数量,V为背包体积。
	for(int i=1;i<=N;i++)
	cin>>v[i]>>w[i];
	for(int i=1;i<=N;i++){
		for(int k = 1;k<=V;k++){//顺向,要用到新数据。
			if(k>=v[i])//可以从v[i]开始省掉一次判断(优化。
			dp[k] = max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

非常的奇妙。


多重背包问题(要变成01背包问题吗?)

直接拆成01背包问题是可以的,也可以多加一层循环。

for(int l=0;l<=s[i]&&l*v[i]<=k;l++)

还有感觉非常帅气,短小精悍的saber简化代码。

#include <bits/stdc++.h>
using namespace std;
int dp[1005],n,t,v,w,s;
main()
{
    cin>>n>>t;
    while(n--)
    {
    cin>>w>>v>>s;
    while(s--)
    for(int j=t;j>=w;j--)
    dp[j]=max(dp[j],dp[j-w]+v);
    }
    cout<<dp[t];
}

二维费用背包问题(有坑点)(待续)