完全背包

⬅ 返回

1、闫氏DP分析法

2、例题

3、思路

关系式推理

4、代码

二维dp[N][N]

#include<iostream>
//#include <algorithm>
using namespace std;
const int N = 1101;
int dp[N][N];
int n,m;
int v[N];
int w[N];
 
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(v[i]<=j)
            {
		            ---------------------------------------------------
                dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
                ------------------------------------------------
                //01背包这里是
                //dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
    
    
}

一维优化dp[N]

#include<iostream>
//#include <algorithm>
using namespace std;
const int N = 1101;
int dp[N][N];
int n,m;
int v[N];
int w[N];
 
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    
    for(int i=1;i<=n;i++)
    {
        //这里要分辨和01背包问题的区别
        // 01背包是从m开始 用的是上一轮的数据
        // 完全背包是从w[i]开始 先更新这一轮的数据 然后用更新的数据继续向后更新
        for(int j=w[i];j<=m;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        /*
	        01背包代码
	        for(int j=V;j>=v[i];j--)
		        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//用上一轮的数据更新这一轮 所以j要从大到小
		        } 
        */
         
    }
    cout<<dp[n][m]<<endl;
    
    
}