01背包:

假设有 n 件物品,至多可装入容积为 m 的容器当中,试问最大可装入的价值为多少?

设w[ i ]为第 i 件物品重量,v[ i ]为第i件物品价值

dp[ i ][ j ]表示将前i件物品装入重量 j 的容器当中

dp方程:

  • 当 i = 0时,dp[ 0 ][ j ]表示把前0件物品装入j大小的容器,总价值为0,所以dp[ 0 ][ j ] = 0
  • 当 j = 0时,dp[ i ][ 0 ]表示把前i件物品装入0大小的容器,总价值为0,所以dp[ i ][ 0 ] = 0
  • 当 j < w[ i ] 时,第 i 件物品无法装入,dp[ i ][ j ] = dp[ i-1 ][ j ]
  • 当 j >= w[ i ]时,dp[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i -1 ][ j-w[ i ]] + v[ i ] )

样例输入:

  • 第一行:物品总数n
  • 第二行:最大容量full
  • 第三行:n个物品的重量
  • 第四回:n个物品的价值

5
10
2 2 6 5 4
6 3 5 4 6

样例输出:

  • 最大可装入价值

15

dp状态表

i \ j012345678910
000000000000
100666666666
200669999999
300669999111114
4006699910111314
500669121212151515

代码模板:

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1001//物品最大数 
#define MAXM 1001//重量最大数 
int dp[MAXN][MAXM];//dp数组 
int w[MAXN],v[MAXN];//重量和价值数组 
int n;//物品数量
int full;//最大可装重量 
void solve();//解题函数 
int main(){
	cin>>n;//输入数量
	cin>>full;//输入重量  
	for(int i=1;i<=n;i++){
		cin>>w[i];//输入重量 
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];//输入价值 
	}
	solve(); 
	return 0;
}
void solve(){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=full;j++){
			if(i==0 || j==0) dp[i][j]=0;//边界dp,结果为0 
			else{
				if(j<w[i]) dp[i][j]=dp[i-1][j];//装不下 
				else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//装得下,max比较装或不装哪个更大 
			}
		}
	}
	cout<<dp[n][full]<<endl;//输出结果 
}

空间优化:

由于算法时间复杂度已经无法优化,但我们可以考虑优化空间复杂度

从上述代码我们可以看出,dp数组每次都是调用前一轮dp的结果,因此可以采用滚动数组来保存决策量

dp方程: 

只需要修改dp[ i ][ j ]修改为dp[ i%2 ][ j ]

因此,dp[ i -1 ][ j ]修改为dp[ (i-1)%2 ][ j ]

初始化 i = 0,每轮dp之后 i += 1 

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1001//物品最大数 
#define MAXM 1001//重量最大数 
int dp[2][MAXM];//dp数组 
int w[MAXN],v[MAXN];//重量和价值数组 
int n;//物品数量
int full;//最大可装重量 
void solve();//解题函数 
int main(){
	cin>>n;//输入数量
	cin>>full;//输入重量  
	for(int i=1;i<=n;i++){
		cin>>w[i];//输入重量 
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];//输入价值 
	}
	solve(); 
	return 0;
}
void solve(){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=full;j++){
			if(i==0 || j==0) dp[i%2][j]=0;//边界dp,结果为0 
			else{
				if(j<w[i]) dp[i%2][j]=dp[(i-1)%2][j];//装不下 
				else dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-w[i]]+v[i]);//装得下,max比较装或不装哪个更大 
			}
		}
	}
	cout<<dp[n%2][full]<<endl;//输出结果 
}

 

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐