动态规划背包问题

洛谷P1048采药

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 1010, M = 110;
int t[N], w[M];
int f[M][N];//f[i][j]表示前采i个草药前js内能采的最大价值 
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> t[i] >> w[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (j < t[i])f[i][j] = f[i - 1][j];
			else f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + w[i]);
		}
	}
	cout << f[m][n] << endl;

	return 0;
}

降维后： 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 1010, M = 110;
int t[N], w[M];
int f[N];//f[i][j]表示前采i个草药前js内能采的最大价值 
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> t[i] >> w[i];
	}
	for(int i = 1; i <= m; i++){
		for(int j = n; j >= t[i]; j--){
			f[j] = max(f[j], f[j - t[i]] + w[i]);
		}
	}
	cout << f[n] << endl;
	
	return 0;
} 

洛谷P1616疯狂采药：注意范围会爆int

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 10010, M = 1e7 + 10;
int t[N], w[N];
long long f[M];//注意要long long 
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> t[i] >> w[i];
	}
	for(int i = 1; i <= m; i++){
		for(int j = t[i]; j <= n; j++){
			f[j] = max(f[j], f[j - t[i]] + w[i]);
		} 
	} 
	cout << f[n] << endl;
	
	return 0;
} 

洛谷P1164小A点菜

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 110, M = 10010;
int a[N];
int f[N][M];//f[i][j]表示前i种菜剩余j元最多点菜方案数 
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)cin >> a[i];
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(j == a[i])f[i][j] = f[i - 1][j] + 1;
			if(j > a[i])f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]];
			if(j < a[i])f[i][j] = f[i - 1][j];
		}
	}
	cout << f[n][m] << endl;
	return 0;
} 

 类似01背包做法

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 110, M = 10010;
int a[N];
int dp[N][M];
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)cin >> a[i]; 
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			//只点第i道菜 
			if(j == a[i])	dp[i][j] = 1;
			if(j - a[i] >= 0){
				//点第i种菜 
				dp[i][j] = dp[i][j] + dp[i - 1][j - a[i]] + dp[i - 1][j];
			}
			else{
				//不点第i种菜 
				dp[i][j] = dp[i][j] + dp[i - 1][j];
			}
		}
	}
	cout << dp[n][m] << endl;
	return 0;
} 

记忆化搜索做法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[105][10005],n,m,v[105],ans;
LL dfs(LL c,LL k)
{
    if(f[c][k])return f[c][k];
    if(v[c]>k)return 0;
    if(v[c]==k)return 1;
    for(LL i=c+1;i<=n;i++)f[c][k]+=dfs(i,k-v[c]);
    return f[c][k];
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;i++)scanf("%lld",&v[i]);
    for(LL i=1;i<=n;i++)ans+=dfs(i,m);
    printf("%lld\n",ans);
    return 0;
}