背包

01背包(每个物品只能用一次)

v表示 体积 w表示 价值.

DP

1. 状态表示(用几维数组表示状态),背包问题一般为二维.

f( i , j )表示一个神奇的函数可以替我们解决DP问题.

f ( i , j )：

• 集合:所有选法or有条件(只从前i个物品选&&总体积小于j).

• 属性(一般为maxn,minn,数量)).

• 状态计算(状态转移方程)

• 集合划分

f ( i , j )：从i-1到j(包含i)

f ( 1 , i-1 )：从1到i(不包含i)(可能不存在)

整个问题的解 res=max( f (1 , i-1 ) , f ( i-1 , j ) ).

一维

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;

int n,m;
int v[N],w[N];
int f[N];

int main()
{
  scanf("%d%d",&n,&m);

  for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

  for(int i=1;i<=n;i++)
  {
    for(int j=m;j>v[i];j--)
    {
        f[j]=max(f[[j],f[j-v[i]]+w[i]);
    }
  }

  printf("%d",f[m]);

  return 0;
}

练手题

1. 开心的金明

2. 采药

3. 01背包问题