题意

一个背包。

m是背包容量。

n是物品个数。

$p_i$是第i个物品的价值。

$t_i$是第i个物品的体积。

因为物品没有数量限制。

所以是完全背包。

思路

完全背包。

直接滚动数组。

因为状态是第几个物品。

所以二维数组压n。

代码

#include<iostream>
using namespace std;
struct{
	int p;
	int t;
}a[int(2e4)]{
	
};
int f[int(2e4)]{
	
};
int main(){
	int m(0);
	int n(0);
	cin>>m>>n;
	for(int i(1);i<=n;i++)
		cin>>a[i].p>>a[i].t;
	for(int i(1);i<=n;i++)
		for(int j(a[i].t);j<=m;j++)
			f[j]=max(f[j],f[j-a[i].t]+a[i].p);
	cout<<f[m];
	return 0;
}

提醒

1. 这个题目不能用dfs，会T。
2. 这个题目不要听 @ 胡扯，dp是可以的。只是他的歹马有问题。

这个只能用dp,dfs会tle,如下:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[10005],c[10005];
int dp[10005][10005]={};
int dfs(int i,int sp){
	if(i==0||sp==0) return 0;
	if(dp[i][sp]) return dp[i][sp];
	if(w[i-1]>sp)dp[i][sp]=dfs(i-1,sp);
	else dp[i][sp]=max(dfs(i-1,sp),dfs(i-1,sp-w[i-1])+c[i-1]);
	return dp[i][sp];
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>w[i]>>c[i];
	cout<<dfs(n,m)<<"\n";
	return 0;
}

这道题需要空间优化做，否则74ac，如下:

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> p,t;
//int p[10005],t[10005];
//int vst[10005][10005]={};
int main(){
	cin>>m>>n;
	for(int i=0,x,y;i<n;i++){
		cin>>x>>y;
		p.push_back(x);
		t.push_back(y);
	}
	vector<vector<int> > vst(n+1,vector<int>(m+1,0));
	for(int i=1;i<=n;i++){
		for(int c=1;c<=m;c++){
			if(t[i-1]>c) vst[i][c]=vst[i-1][c];
			else vst[i][c]=max(vst[i-1][c],vst[i][c-t[i-1]]+p[i-1]);
		}
	}
	cout<<vst[n][m]<<"\n";
	return 0;
}

所以直接抄军舰的呆马

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int n,m;
//vector<int> p,t;
int p[10005],t[10005];
//int vst[10005][10005]={};
int main(){
	cin>>m>>n;
	for(int i=0;i<n;i++) cin>>p[i]>>t[i];
	vector<int> dp(m+1,0);
	for(int i=1;i<=n;i++){
		for(int c=1;c<=m;c++){
			if(t[i-1]>c) dp[c]=dp[c-1];
			else dp[c]=max(dp[c],dp[c-t[i-1]]+p[i-1]);
		}
	}
	cout<<dp[m]<<"\n";
	return 0;
}

你以为这就结束了？？？

这个代码是92ac，所以还是不行

因此！只需要一起用dfs和dp！

在开始算法之前先判断一下数据大小

如果不会超时就用dfs，反之dp

综合一下代码如下:

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[10005],t[10005];
int vst[10005][10005];
int dfs(int i,int c){
	if(!i||!c) return 0;
	if(vst[i][c]) return vst[i][c];
	if(c<t[i-1]) return dfs(i-1,c);
	int ys=dfs(i,c-t[i-1])+p[i-1];
	int no=dfs(i-1,c);
	vst[i][c]=max(ys,no);
	return vst[i][c];
}
int Dp(int nn,int mm){
	vector<int> dp(m+1,0);
	for(int i=1;i<=nn;i++){
		for(int c=1;c<=mm;c++){
			if(t[i-1]>c) dp[c]=dp[c-1];
			else dp[c]=max(dp[c],dp[c-t[i-1]]+p[i-1]);
		}
	}
	return dp[mm];
}
int main(){
	cin>>m>>n;
	for(int i=0;i<n;i++) cin>>p[i]>>t[i];
	if(n<=2005)cout<<dfs(n,m)<<"\n";
	else cout<<Dp(n,m)<<"\n";
	return 0;
}