题目描述
实现一个算法求解 01 背包问题。背包问题的介绍如下：

已知一个容量为 totalweight 的背包，有不同重量不同价值的物品，问怎样在背包容量限制下达到利益最大化。

01 背包问题要求每个物品只有一个，可以选择放入或者不放入背包。

背包问题求解方法的介绍如下：

用符号 V_i 表示第 i 个物品的价值，W_i 表示第 i 个物品的体积，V_{i,j} 表示当前背包容量为 j 时，前 i 个物品最佳组合对应的价值。

对于当前第 i 个商品，如果包的容量比该物品体积小，即 j < W_i。那么此时的价值与前 i-1 个的价值是一样的，即 V_{i,j} = V_{i-1,j}。

对于当前第 i 个商品，如果包的容量能够装下该物品，即 W_i \le j。此时需要判断装或者不装这个物品的价值对比，选择使价值更大的情况，即 V_{i,j} = \max(V_i + V_{i-1,j-W_i},\ V_{i-1,j})。

通过最优解回溯法找到解的组成：

当 V_{i,j} = V_{i-1,j} 时，说明没有选择第 i 个物品。

当 V_{i,j} = V_{i-1,j-W_i} 时，说明装了第 i 个商品。

从 i、j 的最大值一直遍历到 i=0，则找到了所有解。

输入描述
第一行为两个数字 totalweight、N，均不超过 1000。totalweight 含义见题干，N 为物品数量。
接下来 N 行，每行两个数字 W_i、V_i，均不超过 1000。含义见题干。

输出描述
输出一行，为在背包容量限制下的最大化利益。

输入输出样例
示例
输入
8 5
3 4
5 5
1 2
2 1
2 3
输出
10

题目简要

题目要求一个一定容量的背包内，尽可能塞入价值足够大而且总容量不超过背包容量的前提下，求最大价值

解题思路

还是那句话，这种求最大的应用题，随便举几个例子，看看贪心能不能用，在这里贪心是绝对不可用的，如果说按照贪心来说的话，贪心选择的是单位容量下的价格最高的那一个，盯着眼前性价比最高，而这道题是组合问题，性价比最高的可能会造成浪费，就比如背包总容量为10，三个商品的容量分别为6，5，5，价值为10，6，6，在背包有限的情况下按照贪心选最有性价比的话应该选(6,10)这一组，但是显然它不能使背包装满，如果说我选两个5的话就能在装满的同时实现了效应最大化。

所以该用什么?

这道题，前一步选择的与后一步选择强相关，前一步选择会在下一次选择的时候被使用，而且每一次都是这样，这明显符合DP动态规划

DP动态规划

DP动态规划里面有个dp数组，这个dp数组会在程序运行中不断改变，每一次改变都是最优的，当最后一次改变后里面的全部元素都是最优元素，那在这道题中dp数组要如何定义，我们需要找一个数值不变而且从程序开始到程序结束它的属性都不会变化的一个对象来搭建dp数组中每个元素的定义，而且一般程序结束后在dp数组中找到最优，所以说数组元素的值应该是题目所求。

在这里，题目中给出了背包容量不大于1000，也就代表着，背包总容量在1到1000中选其一，而且背包容量在程序开始与结束都是不会变化的，所以说我们不妨令dp[1000]，题目中要求最优价值，也就是dp中每一个值都是这个背包容量下的最优价值。

拿到了dp数组定义之后，就是怎么对数据进行处理，在这里商品个数是不少于1000的，也就代表着，我能用一个数组来存放对应的商品和它的价值，我定义了一个List[1000]，其中List[4]=100，代表着这个商品占用4单位空间，价值100，但是又存在一些问题，加入出现了(2,4)(2,5)这种数据怎么呢，那我可以选最大的放进这个数组中去

上面的想法是错误的，我忽视了一个问题，如果这个商品只有两个，分别是(2,4)(2,5)，背包空间有4，由于我在写入2的时候把4抛弃掉了，所以背包中只能放一个商品，它的价值为5，这显然是错误的，答案应该是两个都选才能实现价值最大化（2，4）代表着占据2空间价值为4

所以存放每一组数据应该要用两个数组，一个w[1000]用来存放占的容量，一个v[1000]用来存放价值，他们对应元素的键就是他们商品的编号。值就是对应容量和价值

算法的实现

一开始dp里面都是0，我们遍历一下每一个商品的容量和价值，当一个商品为(3,3)时，除了3以前的那些数字之外，每一个大于等于3的dp都能装下，所以dp[1000]=[0,0,3,3,3,3,3,3,…,3]

接着有第二个物品(4,5)

这时候有两种选择，一种是要这个物品，一种是不要这个物品，如果说我要的话，那我加上这个物品之后的价值要大于我原先的价值我才会要，假设我背包空间为8，我不要这个物品的时候背包只占用了4，4占用对应的价值为3，3再加上5，那么加上这个物品的价值就为8，与原先dp[8]=3还要多，所以我选择要这个物品

为什么要那么想呢，我们已经定义了dp[x]是x容量下的最优价值，那么我在选这个物品(4,5)的时候，要占用4个空间，8空间的背包减去4个空间就是我们在拿下这个物品之前使用了的空间，使用的4空间的最优价值就是dp[4],dp[4]加上这个商品的价值再与之前我们算的最优的dp[8]比较，如果说dp[4]+5大于dp[8],那么dp[4]+5才是dp[8]最优的，则其值赋值给，如果不大于则保留一开始的dp[8],这个思想是从一开始定义dp的含义的延申。

下面是代码的实现

#include <stdio.h>
#define MAX 1005   // 数组最大容量，题目限制不超过1000，多开5个防止越界

int dp[MAX];        // dp[j]：背包容量为j时，前面物品能得到的最大价值
int w[MAX], v[MAX]; // w[i]：第i个物品的重量；v[i]：第i个物品的价值

int main(void)
{
    int totalweight, N;
    scanf("%d %d", &totalweight, &N);  // totalweight：背包总容量；N：物品总数

    for(int i = 1; i <= N; i++)
    {
        scanf("%d %d", &w[i], &v[i]);  // 依次读入第i件物品的重量、价值
    }

    // 遍历每一件物品
    for(int i = 1; i <= N; i++)
    {
        // 倒序遍历背包容量，防止同一个物品重复选取（01背包核心）
        for(int j = totalweight; j >= w[i]; j--)
        {
            // 选择这件物品：剩余容量j-w[i]的最优价值 + 当前物品价值
            // 和不选这件物品的原有dp[j]对比，取更大值
            if(dp[j - w[i]] + v[i] > dp[j])
            {
                dp[j] = dp[j - w[i]] + v[i];
            }
        }
    }
    printf("%d", dp[totalweight]);  // 输出容量为totalweight的背包能拿到的最大价值
    return 0;
}