01背包问题是一种动态规划问题：
给定 n 个物品，每个物品有重量 w[i] 和价值 v[i ] ，以及一个容量为 X 的背包。要求在不超过背包容量的前提下，选择物品使得总价值最大。（每个物品只能选择一次或不选）
解法：
-
定义一个 dp 数组，设 dp[i][j] 表示前 i 个物品中，容量为 j 的背包能装的最大价值。
状态转移方程（核心点） -
如果不选第 i 个物品, dp[i][j] = dp[i - 1][j]
-
如果选择第 i 个物品，dp[i][j] = dp[i - 1][j - w[i]] - v[i]
综合以上来看，若想要求出最大值，则：
- dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] - v[i])
废话不多说，代码模板：
#include<bits/stdc++.h>
using namespace std;
int dp[][];
//定义dp数组
int n, x;
//初始化
int w[];
//存储质量
int v[];
//存储价值
int main(){
//输入
for(int i = 1;i <= n;i++){//遍历前i个物品
for(int i = 1;i <= x;i++){//遍历质量
if(j < w[i]){//如果这些载质量不够装这个物品
dp[i][j] = dp[i - 1][j];//就只能不装
continue;
}
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);//状态转移方程
}
}
cout << dp[n][x];
//输出答案（从前n个物品选择，载质量为x）
return 0;
}