一、 [NOIP2001]装箱问题

描述
有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述：
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出描述：
1个整数，表示箱子剩余空间。

解法:

设计状态表示前n个物体放在V中的最大体积是多少。

#include
#include
using namespace std;
int main()
{
    int n;
    int v;
    cin >> v;
    cin >> n;//dp[v]的意思为：容量为v时，能装的最大体积。
    vector<int>dp(v+1,0);//本质还是01背包问题，剩余空间最小就是价值最大的意思。01背包算出能装最多的空间，
    vector<int>volum(n);//再用v-dp[v]就得剩下的最小空间。
    for(int i = 0;i < n;i++)
        cin >> volum[i];
    for(int i = 0;i < n ;i++)
    {
        for(int j = v;j >= volum[i];j--)
        {
            dp[j] = max(dp[j],dp[j-volum[i]] + volum[i]);
        }
    }
    cout << v-dp[v] <<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二、【模板】01背包

描述
你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为vi ,价值为wi 。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数vi和wi ，表示第i个物品的体积和价值。

1≤n,V,vi,wi ≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

解法:（动态规划）

1.解题思路
第一问：

状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。
状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j])

第二问：

状态定义：dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品。
状态初始化：将背包容量为0的情况设置价值为0，其它情况设置为最小的Integer型整数，表示不可达状态。后续所有的状态都需要从为0的状态转移过去。
状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即dp2[j]=Math.max(dp2[j−v[i]]+w[i],dp2[j])。

#include 
#include 
#include 

using namespace std;

const int N = 1010;

int f[N]; // f[j]表示体积为j的情况下的总价值
int v[N], w[N]; // 物品的体积 价值

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    memset(f, -0x3f, sizeof f);  //一开始都初始化为负无穷  方便记录是否有恰好体积为j的情况出现过  
    f[0] = 0; // 最开始体积为0价值为0
    for(int i = 1; i <= n; i ++) 
        for(int j = m; j >= v[i]; j --) // j>=v[i] 保证了可以选择第i个物品
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]); // 这里其实消去了一维
           // 原式为f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
           // 为了防止计算时所需要的上一层的数值被覆盖所以倒序遍历这样算f[j]时用到的f[j - v[i]]就还是和原来一样
        }
    
    int ans1 = 0, ans2 = 0;
    for(int i = 0; i <= m; i ++) ans1 = max(ans1, f[i]); // 找到最大值
    
    if(f[m] < 0) ans2 = 0; // 如果f[m]<0说明没被初始化过 没有体积恰好为m的情况出现
    else ans2 = f[m];  //否则根据定义可知 f[m]的值就是背包恰好装满的情况下的最大值
    
    cout << ans1 << endl;
    cout << ans2 << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

三、【模板】完全背包

描述
你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为vi,价值为wi。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数vi 和wi
​
，表示第i种物品的体积和价值。
1≤n,V≤1000

输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

解法:

基本思路与01背包问题相同。唯一不同的是，题目中的物品可以重复加入，而01背包问题中要避免物品重复加入。
在01背包问题中，避免重复添加一件物品是通过逆序遍历来实现的，而在本题中要包含重复添加一件物品的情况，只需将逆袭改为正序遍历即可。

#include 
#include 

using namespace std;

int main(){
    int n, v;
    cin >> n >> v;
    vector<int> pa(n);
    vector<int> va(n);
    for(int i = 0;i < n;i++){
        cin >> va.at(i) >> pa.at(i);
    }
    vector<int> res(v + 1, 0);
    vector<int> cres(v + 1, -99999);
    cres.at(0) = 0;
    for(int i = 0;i < n;i++){
        for(int j = va.at(i);j <= v;j++){
            res.at(j) = max(res.at(j), res.at(j - va.at(i)) + pa.at(i));
            cres.at(j) = max(cres.at(j), cres.at(j - va.at(i)) + pa.at(i));
        }
    }
    int max = res.at(v);
    int cmax = cres.at(v) > 0 ? cres.at(v) : 0;
    cout << max << endl << cmax;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28