01背包题目链接
题意：有一个容量为m的背包以及n个可以拿的物品，给出n个物品的体积和价值，要求输出可以拿的最大价值
思路：
代表在前i件物品中拿取总体积不超过j的最大价值
由此可以分情况讨论状态转移
当j<v[i]时，说明当前枚举的重量本身就不足以拿取当前物品，则
如果j>v[i]，则分为拿当前物品和不拿当前物品
如果拿，则有
如果不拿，则有
ac代码：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=1010;
int v[N];
int w[N];
int dp[N][N];
int n,m;
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//依次读入每个物品的价值和重量for(int i=1;i<=n;i++)//遍历拿前i件物品{for(int j=0;j<=m;j++)//遍历最大容量j{if(j<v[i])dp[i][j]=dp[i-1][j];//当前容量不足以拿当前物品else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);}}cout<<dp[n][m]<<endl;}
signed main()
{Mirai;int T=1;//cin>>T;while(T--){solve();}
}一维优化：
不难发现，更新选前i件物品时，状态转移所需要的状态只来自i-1，所以完全可以不必将所有状态全部保存下来，只需要将数组开到一维即可
优化后的状态转移方程为：
if(j<v[i])dp[j]=dp[j]; else dp[j]=max(dp[j],dp[j-v[i]]+w[i]);其中，dp[j]更新状态所需要的状态是未更新的左边的值，这就要求我们在更新j的时候其中小于j的值是保证不能被更新的，所以我们需要从大到小进行遍历，而其中j<v[i]的部分的值是直接保留的，所以可以将遍历范围规定到(m~v[i])
ac代码：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=1010;
int v[N];
int w[N];
int dp[N];
int n,m;
void solve()
{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>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[m]<<endl;
}
signed main()
{Mirai;int T=1;//cin>>T;while(T--){solve();}
}
