记得以前老师上来就dp直接搞蒙了，穷举可能更好理解些...

dp解主要是要搞懂递推方程式的推出过程，找到状态转移函数

题目

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

第 i 件物品的体积是 vi，价值是 wi。

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

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

dp解

#include <iostream>

const int MAXN = 1005;

int weight[MAXN] = {1, 2, 3, 4, 5}; // 重量
int value[MAXN] = {10, 20, 30, 40, 50}; // 价值
int f[MAXN][MAXN]; // f[i][j], j重量下前i个物品的最大价值

using namespace std;

int main()
{
    int itemTot = 5; // 5个物品
    int weightLimit = 10; // 最大装10重量

    for (int i = 1; i <= itemTot; i ++) {
        for (int j = 1; j <= weightLimit; j ++) {
            // 当前重量装不进，价值等于前i - 1个物品
            if (j < weight[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                // 能装，需判断
                f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]);
            }
        }
    }

    cout << f[itemTot][weightLimit] << endl;
    return 0;
}

穷举解

#include <iostream>
#include <vector>

using namespace std;

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

void combine2( int n, int m,  vector<int> b, vector< vector<int> > *arr);
void print_arr(vector< vector<int> > *);
int get_max_value(vector< vector<int> > *arr, int weightLimit);

const int MAXN = 1005;

int weight[MAXN] = {1, 2, 3, 4, 5}; // 重量
int value[MAXN] = {10, 40, 30, 20, 50}; // 价值
int f[MAXN] = {0}; //  j重量下任选前i个物品的最大价值，集合

int main()
{
    int itemTot = 5; // 5个物品
    int weightLimit = 10; // 最大装10重量

    // 从n个物品中任选1-n个，排列组合，求得选某几个物品的价值最大值
    for (int i = 1; i <= itemTot; i ++) {
        vector< vector<int> > result;
        
        vector<int> b(i);
        combine2(itemTot, b.size(), b, &result);
        // print_arr(&result);
        f[i] = get_max_value(&result, weightLimit);
    }

    cout << *max_element(begin(f), end(f)) << endl;
    return 0;
}

int get_max_value(vector< vector<int> > *arr, int weightLimit)
{
    int maxValue = 0;
    for(int i = 0; i < (*arr).size(); i ++) {
        int valueTot = 0;
        int volumeTot = 0;
        for (int j = 0; j < (*arr)[i].size(); j ++) {
            valueTot += value[(*arr)[i][j]];
            volumeTot += weight[(*arr)[i][j]];
        }
        if (volumeTot <= weightLimit) {
            maxValue = max(maxValue, valueTot);
        }
    }
    return maxValue;
}

void combine2(int n, int m,  vector<int> b, vector< vector<int> > *arr) {
    for(int i = n; i >= m; i --) {
        b[m - 1] = i - 1;
        if (m > 1){
            combine2(i - 1, m - 1, b, arr);
        } else {
            arr->push_back(b);
        }
    }
}

void print_arr(vector< vector<int> > *arr)
{
    for (int i = 0; i < arr->size(); i ++) {
        cout << "第" << i << "组数进行输出" << endl;
        for ( int j = 0; j < (*arr)[i].size(); j ++) {
            cout << (*arr)[i][j] << " ";
        }
        cout << endl;
    }
}

参考资料

1. https://stackoverflow.com/questions/7719978/finding-max-value-in-an-array
2. http://www.cplusplus.com/reference/vector/vector/clear/
3. http://www.voidcn.com/article/p-nnocitow-bca.html
4. https://www.acwing.com/solution/acwing/content/1374/
5. https://www.acwing.com/problem/content/description/2/
6. https://zhuanlan.zhihu.com/p/30959069