01背包问题：

给定一个有一定容量的背包，和n个物品，每个物品只能选择一次。

成都创新互联拥有10多年成都网站建设工作经验,为各大企业提供成都网站建设、成都网站制作服务，对于网页设计、PC网站建设（电脑版网站建设）、手机APP定制开发、wap网站建设（手机版网站建设）、程序开发、网站优化（SEO优化）、微网站、域名注册等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了很多网站制作、网站设计、网络营销经验，集策划、开发、设计、营销、管理等网站化运作于一体，具备承接各种规模类型的网站建设项目的能力。

每个物品有其对应的体积和价值。

问背包最多能装下的物品的大价值为多少。

输入格式：

第一行两个整数，N，V，分别表示物品数量和背包容积。

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

输出格式：

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

思路：

假设f[i][j]代表当只选择前n个物品并且背包容量只有j的时候所能装下物品的大价值

f[i][j] = max(f[i - 1][j]，f[i - 1][j - v[j]] + w[j])

题目的答案就是f[n][m]。

为什么这样做是正确的呢：

当我们在面对第i件物品的时候，我们一定会在选择第i件物品和不选择第i件物品这两种情况中做出选择。

集合的角度：

假设我们有一个集合，集合表示的是只看前i件物品，背包容量为j的时候的所有物品选法，f[i][j]取集合中的大值，该集合可以划分为选择第i件物品和不选择第i件物品两个集合，f[i][j]取两个集合中的大值即可。

选和不选两种情况下状态的改变：

如果我们不选择第i件物品，那么我们的背包的价值就不变，等于f[i-1][j]。

如果我们背包的容量足够，我们选择第i件物品的话，虽然我们得到了第i件物品的价值，但是我们背包的体积一定会损耗，体积如果损耗，那么我们就有可能放下前面已经装进背包中的物品，此时我们的背包价值是不一定增大的。

所以我们的f[i][j]取两者的大值，也就是

f[i][j] = max(f[i - 1][j]，f[i - 1][j - v[j]] + w[j])

给出图示：

代码如下：

#includeusing namespace std;
const int N = 1010;
int v[N], w[N];//每个物品的体积和价值
int f[N][N];//每个状态的大价值
int n, V;//物品数和背包容量
int main() {
    cin >>n >>V;
    for (int i = 1; i<= n; i++)
        cin >>v[i] >>w[i];

    for (int i = 1; i<= n; i++)
        for (int j = 0; j<= V; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout<< f[n][V];
    return 0;
}

优化至一维：

我们发现，我们在更新的时候只会用到两层状态，每一个状态都是由上一层左边的状态推导而来的，我们不妨将这两行合并。

dp方程为：

f[j] = max(f[j], f[j - v] + w)

一维状态中，f[j]默认就是上一层的f[j]，所以不用进行不选第i个物品的更新。当我们选择第i个物品时当，我们需要用到上一层左边的状态，所以我们不能把本层左边的状态更新成上一层左边的状态。如果我们从前往后进行更新，那么上一层的左边的状态就被更新掉了。所以我们应该从后往前更新。

代码如下：

#includeusing namespace std;
const int N = 1010;
int n, V;//物品数
int v, w;//总体积
int f[N];//状态
int main() {
    cin >>n >>V;
    for (int i = 0; i< n; i++) {
        cin >>v >>w;
        for (int j = V; j >= v; j--)
            if (v<= j)f[j] = max(f[j - v] + w, f[j]);//f[j]默认就是上一行的值,所以不用更新v小于j的情况
    }

    cout<< f[V];
    return 0;
}

注意：

1.背包问题中的状态，无论是一维还是二维，dp数组要同时满足背包体积和物品数量两个边界，而不是满足数量边界即可。

2.状态更新要用到f[i-1]，所以物品下标要从1开始。

例题： 装箱问题：

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

在 n 个物品中，任选若干个装入箱内，使箱子的剩余空间为最小。

输入格式：

第一行是一个整数 V，表示箱子容量(0≤V小于等于20000)。

第二行是一个整数 n，表示物品数(0≤n≤30)。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

思路：

题目要尽可能的装满箱子。我们给每个物品赋予一个价属性，价值的值就是体积的值。所以就是求一定体积下的大价值是多少。

代码如下：

//二维
#includeusing namespace std;

const int N = 20010, M = 40;
int f[M][N];
int n, m;//物品数和背包容量

int main() {
    cin >>m >>n;

    int v, w;
    for (int i = 1; i<= n; i++) {//前i个物品
        //读入体积和价值
        cin >>v;
        w = v;
        for (int j = 0; j<= m; j++) {//体积为j
            f[i][j] = f[i - 1][j];//不选该物品
            if (j >= v)f[i][j] = max(f[i][j], f[i - 1][j - v] + w);
        }
    }

    cout<< m - f[n][m];//记得做减法

    return 0;

}

//一维
#includeusing namespace std;

const int N = 20010;
int f[N];
int n, m;//物品数和背包容量

int main() {
    cin >>m >>n;

    int v, w;
    for (int i = 1; i<= n; i++) {//前i个物品
        //读入体积和价值
        cin >>v;
        w = v;
        for (int j = m; j >= v; j--) {//从后往前更新
            f[j] = max(f[j], f[j - v] + w);
        }
    }

    cout<< m - f[m];//记得做减法

    return 0;

}

注意:最后输出的是剩余多少空间，我们求出来的是大体积，所以不要忘记做减法。

数字组合：

给定 N 个正整数，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入格式

第一行包含两个整数 N 和 M（1≤N≤100，1≤M≤10000）。

第二行包含 N 个整数，表示 A1,A2,…,AN。

输出格式：

包含一个整数，表示可选方案数。

思路：

f[i][j]表示只看前i个物品，和为j的情况。

如果选择第i个物品：f[i][j] = f[i-1][j-v[i]]。

如果不选第i个物品：f[i][j] = f[i-1][j]。

f[i][j]等于两者之和。

该题需要初始化，f[0][0] = 1。

代码如下：

//二维
#includeusing namespace std;

const int N = 110, M = 10010;
int f[N][M];
int n, m;//n个数和为m

int main() {
    cin >>n >>m;

    int v;

    f[0][0] = 1;

    for (int i = 1; i<= n; i++) {//前i个数
        cin >>v;
        for (int j = 0; j<= m; j++) {
            f[i][j] += f[i - 1][j];//不选
            if (j >= v)f[i][j] += f[i - 1][j - v];//选
        }
    }

    cout<< f[n][m];

    return 0;
}

//一维
#includeusing namespace std;

const int M = 10010;
int f[M];
int n, m;//n个数和为m

int main() {
    cin >>n >>m;

    int v;

    f[0] = 1;//初始化

    for (int i = 1; i<= n; i++) {//前i个数
        cin >>v;
        for (int j = m; j >= v; j--)
            f[j] += f[j - v];//选
    }

    cout<< f[m];

    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页标题：动态规划——01背包问题-创新互联
本文链接：http://kswjz.com/article/ipjoi.html