蒜头君的购物袋2——01背包(经典)

法一 二维数组：

时间复杂度: O ( N ∗ V ) O(N*V) O(N∗V)

空间复杂度: O ( N ∗ V ) O(N*V) O(N∗V)

#include<bits/stdc++.h> 
using namespace std;
int v[101];
int p[101];
int dp[101][1010];
int main()
{
	int V,n;
	cin>>V>>n;
	memset(dp,0,sizeof(dp));//数组默认的其实也是0 
	for(int i=1;i<=n;i++){
		cin>>v[i]>>p[i];
	}	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=V;j++){
			if(v[i]>j){
				dp[i][j]=dp[i-1][j];
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+p[i]);					
			}
}
	}
	cout<<dp[n][V]<<'\n';
    return 0;
}
           

法二 优化空间复杂度后：

时间复杂度: O ( N ∗ V ) O(N*V) O(N∗V)

空间复杂度: O ( V ) O(V) O(V)

#include<bits/stdc++.h> 
using namespace std;
int v[101];
int p[101];
int dp[1010];
int main()
{
	int V,n;
	cin>>V>>n;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>v[i]>>p[i];
	}	
	for(int i=1;i<=n;i++){
		for(int j=V;j>=v[i];j--){
				dp[j]=max(dp[j],dp[j-v[i]]+p[i]);
		}
	}
	cout<<dp[V]<<'\n';
    return 0;
}
           

注意：第二层循环是从大到小，从总容量 V V V到 0 0 0进行枚举。

PS:若从小到大进行枚举，则后面的背包 d p [ j ] dp[j] dp[j]在进行最大重要度计算时， d p [ j − v [ i ] ] dp[j-v[i]] dp[j−v[i]]可能是已经加过第i件物品后的值，引发在背包中重复放置同一件物品(一件物品只有一个)，造成错误。这种情况对应的其实是完全背包问题。