一道大水题完全背包模板题

rt，因为每种题目的数量不限，所以这道题使用完全背包dp。 那么这道题其实跟着五步走就行

1. 划分阶段：我们以题目的种类和总耗时来划分
2. 确定状态变量$dp[i]$表示在$i$时间段的最高得分
3. 确定状态转移方程：对于每个$dp[j]$都能通过$dp[j-t[i]]$推出($t[i]$表示第$i$种题目的耗时)，所以我们可以推出状态转移方程为dp[j]=max(dp[j],dp[j-t[i]]+p[i]
4. 设定边界，因为要进行最大值比较，所以设$dp[0]$~$dp[n]$为0，但是如果声明的是全局数组，那么数组会自动将所有变量初始化为0
5. ACCODE：

#include<iostream>
using namespace std;
int m,n,p[10001],t[10001],dp[10001];//三个数组分别表示每个种类的分值，每个种类的耗时，和在耗时i最多能拿多少分
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i]>>t[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=t[i];j<=m;j++)//从t[i]开始，防止越界，到总时间m结束
		{
			dp[j]=max(dp[j],dp[j-t[i]]+p[i]);//比较当前和从前面推来这两个分值的大小
		}
	}
	cout<<dp[m];
}

当我看到一道完全背包模板题时:

用万能神奇耐用善良简单方法深搜做!万一能拿50分呢!

so...

#include <iostream>
using namespace std;

int poi[10001],minu[10001];
int m,n;
int maxn = 0;

void dfs(int sum,int value)//表示时间和和分数和
{
	if(sum > m)//时间超过了即背包装满了
	{
		return;
	}
	if(sum == m)//正好
	{
		maxn = max(maxn,value);//打擂台最大分数即价值
		return;
	}
	for(int i = 1;i <= n;i++)//枚举所有题型
	{
		dfs(sum + minu[i],value + poi[i]);//dfs下去
	}
}

int main()
{
	cin >> m >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> poi[i] >> minu[i];
	}
	dfs(0,0);//两个都从0开始
	cout << maxn;
	return 0;
}

我真的好兴奋居然有这么多分!

正常思路:

确实是完全背包。为啥咧?因为这个本来就是完全背包说了等于没说

1. 首先确定dp数组含义,这里dp[i]含义是当前这个时间能获得的最大分数。
2. 其次确定状态转移方程,可以选择做这题或不做。那么就是dp[j] = max(dp[j],dp[j - time1[i]] + value[i]);//做,不做
3. 再次是初始化,初始成0。
4. 最后是遍历顺序,两个for。i从1到n,j从1到m,但可以做一个小优化就是j可以从time[i]开始,因为看看状态转移方程j需要减去time[i]。
5. 众所周知,节俭是个好习惯,所以我们的dp数组不要留那么多空间、、、开10001就行~勤俭节约,从我做起~

蒟蒻の代码:

#include <iostream>
using namespace std;

int value[10001],time1[10001],dp[10001];

int main()
{
	int m,n;
	cin >> m >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> value[i] >> time1[i];
	}
	
	for(int i = 1;i <= n;i++)
	{
		for(int j = time1[i];j <= m;j++)//遍历
		{
			dp[j] = max(dp[j],dp[j - time1[i]] + value[i]);//状态转移方程
		}
	}
	cout << dp[m];//输出dp[m]
	return 0;
}

#include<iostream>
#include<string>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
using namespace std;
#define LL long long
const int N = 1e7+10;
const int INF = 0x3f3f3f3f;
long long dp[N],n,m,w,v; 
int main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>v>>w;
		for(int j=w;j<=m;j++){
			dp[j]=max(dp[j],dp[j-w]+v);
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}