洛谷 P1048 采药 01背包入门

P1048 采药 

最近想学dp了

一道非常简单入门的01背包，写此博客做一个教训，对01背包还不是特别熟，动态方程很容易就推出来了，但是写二维状态方程时wa了，然后改为一维过了。

主要还是对01背包不熟悉。

dp[i][j] 表示用 j 单位时间采前 i 种药草的最大价值。

dp[i][j] = max( dp[i-1][j-e[i].t] + e[i].w , dp[i-1][j])

但是当 j < e[i].t 时，dp[i][j] = dp[i-1][j] ，。。。就是wa在这儿。

二维代码

#include<bits/stdc++.h>
using namespace std;
const int N=200;
const int T=1e3+100;
int t, m;
struct node{
	int t, w;
}e[N];

int dp[N][T];
int main(){
	cin >> t >> m;
	for(int i = 1; i <= m ; i++){
		cin >> e[i].t >> e[i].w;
	}

	dp[0][0] = 0;
	for(int i = 1; i <= m; i++){
		for(int j = 0; j <= t; j++){
			if(j >= e[i].t)dp[i][j] = max(dp[i-1][j-e[i].t] + e[i].w,dp[i-1][j]);
			else dp[i][j] = dp[i-1][j];
		}
	}
	
	cout << dp[m][t] << endl;
	return 0;
}

　　一维代码

#include<bits/stdc++.h>
using namespace std;
const int N=200;
const int T=1e4+100;
int t, m;
struct node{
    int t, w;
}e[N];

int dp[T];
int main(){
    cin >> t >> m;
    for(int i = 1; i <= m ; i++){
        cin >> e[i].t >> e[i].w;
    }

    dp[0] = 0;
    for(int i = 1; i <= m; i++){
        for(int j = t; j >= e[i].t; j--){
            dp[j] = max(dp[j-e[i].t] + e[i].w,dp[j]);
        }
    }
    
    cout << dp[t] << endl;
    return 0;
}