23/3/6学习记录（背包九讲！）

1. 01背包问题

有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

方程：f [ i ][ j ] = max( f [ i -1 ][ j ] , f [ i -1 ][ j - v[ i ] ] + w[ i ] )

#include <stdio.h>

int max(int a,int b)
{
  return a>b?a:b;
}

const int N=1010；
int f[N][N];
int v[N],w[N];
int n,m;

int main()
{
  scanf("%d %d",&n,&m)
  for(int i=1;i<=n;i++)
	scnaf("%d %d",&v[i],&w[i]);
  for(int i=1;i<=n;i++)//i从1开始，变量已经初始化为0
  {
	for(int j=1;j<=m;j++)
	{
	  f[i][j]=f[i-1][j];
	  if(j>=v[i])
		f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
	}
  }
  int res=f[n][m];
  return 0;
}
/*如果是一维数组优化则是
for(int i=0;i<=n;i++)
	for(int j = m; j >= v[i]; j--)
		f[j]=max(f[j],f[j-v[i]] + w[i])
int res=f[m];
*/

2. 完全背包问题

有 N 件物品和一个容量为 V 的背包，每件物品可以被选无数次，要求在有限的背包容量下，装入的物品总价值最大。

方程：f [ i ][ j ] = max( f [ i -1 ][ j ] , f [ i ][ j - v[ i ] ] + w[ i ] )

#include <stdio.h>
int max(int a,int b)
{
  return a>b?a:b;
}

const int N=1010;
int f[N][N];
int v[N],w[N];
int n,m;

int main()
{
  scanf("%d %d",&n,&m)
  for(int i=1;i<=n;i++)
	scnaf("%d %d",&v[i],&w[i]);
  for(int i=1;i<=n;i++)
  {
	for(int j=1;j<=m;j++)
	{
	  f[i][j]=f[i-1][j];
	  if(j>=v[i])
		f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
	}
  }
  int res=f[n][m];
  return 0;
}
/*一维数组优化
for(int i=0;i<=n;i++)
	for(int j = v[i]; j <= m; j++)
		f[j]=max(f[j],f[j-v[i]] + w[i])
int res=f[m];
*/

3. 多重背包问题

有 N 件物品和一个容量为 V 的背包，第 i 种物品最多有 si 件，每件体积是vi，价值是 wi ，要求在有限的背包容量下，可将那些物品装入使装入的物品总价值最大，输出最大价值。

方程:f [ j ]=max{ f [ j ], f [ j - v [ i ] ] + w[ i ], f [ j - 2*v [ i ] ], ... }

/*
f[i]是总体积为i的情况下，最大价值
for(int i=0;i<n;i++)
{
	for(int j=m;j>=v[i];j--)
		f [ j ]=max( f [ j ], f [ j - v [ i ] ] + w[ i ], f [ j - 2*v [ i ] ], ... )
}
*/
#include <stdio.h>
const int N=110;
int n,m;
int f[N];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
	{
	int v,w,s;
	scanf("%d %d %d",&v,&w,&s);
	for(int j=m;j>=0;j--)
		for(int k=1;k<=s&&k*v<=j;k++)
			f[j]=max(f[j],f[j-k*v]+k*w]);
	}
  int res=f[m];
  return 0;
}

4. 混合背包问题

5. 二维费用背包问题

6. 分组背包问题

7. 背包问题求方案数

8. 求背包问题的方案

9. 有依赖的背包问题