01背包问题

有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vivi，价值是 wiwi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

01背包问题可以用动态规划来解决，动态规划的关键是递推公式，也就是状态转移方程

每个物品都有选和不选两种状态，选就是dp[i-1][j-weight[i]]

不选就是dp[i-1][j];

为什么最后的dp[n][v]就是正确答案？

因为动态规划的过程中，前面的过程都在为最后一步服务，计算前i个物品在背包容量为j的情况下的最优解，计算得来的结果保存在dp数组里，下次取用dp[i-1][j-weight[i]]就是准确值，因为随着i的增加，并不会改变之前已经得到的结果，比如考虑第i件物品，dp数组的前i-1行都是不变的，都作为const数据为后面的递推服务

#include <iostream>
using namespace std;// int value[1001];
// int weight[1001];
// int dp[1001][1001];
// int main()
// {
//     int n, v;
//     cin >> n >> v;
//     for (int i = 1; i <= n; i++)
//     {
//         cin >> weight[i] >> value[i];
//     }
//     for (int i = 1; i <= n; i++)
//     {
//         for (int j = 1; j <= v; j++)
//         {
//             if (j >= weight[i])
//             {
//                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
//             }
//             else
//             {
//                 dp[i][j] = dp[i - 1][j];
//             }
//         }
//     }
//     cout << dp[n][v] << endl;
// }
int dp[100001];
int main()
{int n, m;cin >> n >> m;int v, w;while (n--){cin >> v >> w;for (int i = m; i >= v; i--){if (i >= v){dp[i] = max(dp[i], dp[i - v] + w);}}}cout << dp[m] << endl;
}