蓝桥杯 ALGO-21 算法训练装箱问题（动态规划，01背包）

问题描述
　　有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
　　要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
　　第一行为一个整数，表示箱子容量；
　　第二行为一个整数，表示有n个物品；
　　接下来n行，每行一个整数表示这n个物品的各自体积。
输出格式
　　一个整数，表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0

分析：dp[i][j]表示前i件物品选则部分装入体积为j的背包后，背包总共所占的最大体积，
一共有n件物品，那么dp[n][v]就是前n件物品选择部分装入体积为v的背包后，背包总共占有的最大体积
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

#include <iostream>
using namespace std;
int dp[31][20001];
int main() {
    int v, n;
    cin >> v >> n;
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        for(int j = 1; j <= v; j++) {
            if (j >= t) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << v - dp[n][v];
    return 0;
}

#include <iostream>

using namespace std;

int dp[31][20001];

int main() {

int v, n;

cin >> v >> n;

for(int i = 1; i <= n; i++) {

int t;

cin >> t;

for(int j = 1; j <= v; j++) {

if (j >= t) {

dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

} else {

dp[i][j] = dp[i-1][j];

}

cout << v - dp[n][v];

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版