题目描述

DP选择模型
01背包问题：选择

状态表示f(i：前i个物品,j：还剩多少体积)
集合：所有只考虑前i个物品，且总体积不超过j的选法的集合
属性：max

状态计算： 1.所有不选第i个物品的方案
2.所有选i…
1:f(i-1,j)
2:f(i-1,j-vi)+wi
f(i,j)=max(f(i-1,j),f(i-1,j-vi)+wi)

### 算法1：暴力朴素

#include<iostream>

using namespace std;
const int N = 1010;

int n,m;        //n个物体 
int v[N],w[N];  //v:体积的集合 w:价值的集合
int f[N][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=0;j<=m;j++)   //第i个还剩下j的空间
        {
            f[i][j]=f[i-1][j];   // 1的子集
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
        cout<<f[n][m]<<endl;
        return 0;
}



### 算法2：优化为1维(与题目逻辑无关)

#include<iostream>

using namespace std;
const int N = 1010;

int n,m;
int v[N],w[N];  //v:体积 w:价值
int 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=0;j<=m;j++)
        {
            f[j]=f[j];   // 1的子集
            if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
        cout<<f[m]<<endl;
        return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~