标签：背包 int 问题 flag MAXN MAXM define

背包问题

背包，即询问一个背包装最大价值的物品总价值。

01 背包

例题：P1048 采药

想到使用 DP。

\[f_{i,j} = \left\{\begin{matrix} \max f_{i-1,j-c_i} , f_{i-1,j} & j \ge c_i\\ f_{i-1,j} & j < c_i \end{matrix}\right. \]

（公式中，\(f_{i,j}\) 表示使用前 \(i\) 个物品，重量小于 \(j\) 的价值最高量；\(c_i\) 指本物品的重量，\(w_i\) 指本物品的价值）

Code1

#include <iostream>
using namespace std;
#define MAXN 105
#define MAXM 1005
int w[MAXN], c[MAXN];
int f[MAXN][MAXM];
int main()
{
	int v,n;
	cin>>v>>n;
	for(int i=1;i<=n;i++) cin>>c[i]>>w[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=v;j++)
		{
			if(j>=c[i]) f[i][j]=max(f[i-1][j-c[i]]+w[i],f[i-1][j]);
			else f[i][j]=f[i-1][j];
		}
	}
	cout<<f[n][v];
	return 0;
}

Code2

#include <iostream>
using namespace std;
#define MAXN 105
#define MAXM 1005
int w[MAXN], c[MAXN];
int f[2][MAXM];
int main()
{
	int v,n;
	cin>>v>>n;
	for(int i=1;i<=n;i++) cin>>c[i]>>w[i];
	bool flag=true;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=v;j++)
		{
			if(j>=c[i]) f[flag][j]=max(f[1-flag][j-c[i]]+w[i],f[1-flag][j]);
			else f[flag][j]=f[1-flag][j];
		}
		flag=1-flag;
	}
	cout<<f[1-flag][v];
	return 0;
}

标签：背包,int,问题,flag,MAXN,MAXM,define
From： https://www.cnblogs.com/zhangyuyi1218/p/-/Knapsack_problem