01背包问题

⬅ 返回

闫氏DP分析法

1、数据结构

2、例题

3、代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define PI 3.14159
using namespace std;
 
typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e3+15;
const int mod = 1e9+7;
int dp[N][N];//dp[i][j]指的是前i件物品在容量为j的条件下最大价值
int V[N];//第i件物品的体积
int W[N];//第i件物品的价值
 
void solve()
{
	int n,v;
	cin>>n>>v;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		V[i]=a;
		W[i]=b;
	}
	----------------------------------------------------
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=v;j++)
		{
			if(V[i]<=j)//如果放得下当前物品
			{
				//取
				//前i-1件物品在容量j条件下的最大价值dp[i-1][j]
				//和前i-1件物品在容量j-v[i]条件下的价值加上w[i]的价值dp[i-1][j-V[i]]+W[i]
				//中的最大值
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+W[i]);
			}else{//放不下第i件物品
				dp[i][j]=dp[i-1][j];//前i件物品在容量j条件下的最大价值 就等于 前i-1件物品最大价值
			}
			
		}
	}
-----------------------------------------------------------	
	cout<<dp[n][v]<<endl;
 
}
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
    int T = 1;
    while(T--)
    {
        solve();
    }
}

01背包的一维数组优化

1、分析

为什么可以转为一维

为什么要逆序

2、代码

#include <iostream>
using namespace std;
 
int n,V;
const int N = 1e3+10;
int v[N] , w[N];
int dp[N];//dp[j]表示当空间最大为j所能容纳的最大价值
 
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;j>=v[i];j--)//只有当枚举的背包容量j >= v[i] 时才会更新状态，
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V]<<endl;
 
}