完全背包(每个物品能用无限次)

DP

1. 状态表示

2. 集合(所有只考虑前i个物品，且总体积不大于j的所有选法)

3. 属性：Max

4. 状态计算 (集合的划分)

5. 分类(1,2,3,4,5......k-1,k)

f ( i , j ) 曲线救国：

i.去掉k个物品
ii.求Max,f (i-1 , j-k * v[i]);
iii.得到最终结果;

一维

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

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

int main()
{
  cin>>n>>m;

  for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

  for(int i=1;i<=n;i++)
  {
    for(int j=m;j>=0;j--)
    {
      int tmp=j/v[i];
      for(int k=1;k<=tmp;k++)
      {
        if(j>=k*v[i])
        {
          f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);//状态转移方程
        }
      }
    }
  }

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

  return 0; 
}