dp(01背包和完全背包)

01背包

对于01背包，来说就是每个物品只能使用一次。

对于01背包的思考，就是要找到能背包能够容纳的最大。

首先是二维的01背包，这是最原始的背包也是最好理解的，f[i][j]定义就是前i个物品，背包容量为j的最优解，加入背包容量不够(j<v[i])，所有前i个物品的最优值就是前i-1个物品的价值最大值，对应的代码是:f[i][j] = f[i-1][j]，如果背包容量够，就需要选，选第i个物品与不选第i个物品。如果不选就是f[i][j = f[i-1][j]。如果选的就是f[i][j] = f[i-1][j-v[i]]+w[i]所以取到最大价值取max()即可。但是二维的01背包可以进行一维的优化。

所以状态转移方程可以写成f[i][j] = max(f[i-1][j],f[i-1][j]+w[i])

P1048 采药

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这就是典型的01背包问题，药只能用一次。

代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> m >> n;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }          

    cout << f[n][m] << endl;

    return 0;
}

对于二维就比较好理解，对于一维来说就比较难理解了，一维的状态转移方程f[j] = max(f[j],f[j-v[i]]+w[i]) 并且他的遍历是逆序的。为什么是逆序的呢，可以看这篇文章咱就把0-1背包问题讲个通透！ - 知乎 (zhihu.com)

//一维的01背包
#include<bits/stdc++.h>
using namespace std ;
int ti[1005] , pri[1005] ;
int f[1005] ;
int main()
{
    int t , m ;
    cin >> t >> m ;
    for(int i = 1 ; i <= m ; ++i)
        cin >> ti[i] >> pri[i] ;
    for(int i = 1 ; i <= m ; ++i)
        for(int j = t ; j >= 1 ; --j)//逆序
            if(j >= ti[i])
                f[j] = max(f[j] , f[j - ti[i]] + pri[i]) ;
    cout << f[t] ;
    return 0 ;
}

完全背包

就是每一个物品可以多次使用，所以他的二维的状态转移方程就可以f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])所以说还需要一层对k的循环，判断是k*v[i]<j 这就会需要三层循环。但是我们会发现f[i,j] = max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2*v]+2w...)

f[i,j-v] = max( f[i-1,j-v],f[i-1,j-2*v]+w,f[i-1,j-3*v]+2w...)

所以可以写成f[i][j] = max(f[i,j-v]+w,f[i-1][j])

可以先将f[i][j] = f[i-1][j]所以状态转移方程就可以写成f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i])

对于完全背包的一维优化，我们可以看到就是都是关于f[i][]的东西，所以跟01背包的f[i-1][]是逆序因为不能用到已经用过的，所以完全背是都可以因此顺序操作即可。然后对于完全背包的二维一般都有tle的可能性，所以需要优化到一维。

题目P1616 疯狂的采药

P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

#include<bits/stdc++.h>
using namespace std;

constexpr long long N = 1e7+10;
long long times[N],prices[N];
long long f[N];
void solve(){
	long long t,m;
	cin>>t>>m;
	for(long long i = 1;i<=m;i++){
		cin>>times[i]>>prices[i];
	}
	for(long long i = 1;i<=m;i++){
		for(long long j = 1;j<=t;j++){
			f[j] = f[j];
			if(j>=times[i]){
				f[j] = max(f[j],f[j-times[i]]+prices[i]);
			}
		}
	}
	cout<<f[t];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}