动态规划基础 ——装箱问题

题目描述

有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积? (正整数)。要求从? n? 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。?

输入格式

第一行，一个整数，表示箱子容量；? 第二行，一个整数，表示有n个物品；? 接下来n行，分别表示这n个物品的各自体积。?

样例

24
6
8
3
12
7
9
7

0

我的代码

#include <bits/stdc++.h>
using namespace std;
int v[20001]={0};
void findlarge(int m,int n,int a[])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i];j--)
        {
            if(v[j]>v[j-a[i]]+a[i])
            {
                v[j]=v[j];
            }
            else
                v[j]=v[j-a[i]]+a[i];
        }
    }
    cout<<m-v[m]<<endl;
}
int main()
{
    int i,m,n,a[35]={0};
    cin>>m>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    findlarge(m,n,a);
    return 0;
}

?我的解题思路：

作为一个新手，我并不清楚什么是动态规划，但因为学过一些离散数学的知识，简单理解的话，其实动态规划和递推方程之间有点联系

在下面这个博主的博客里面详细的介绍了递归与递推的区别，从某种意义上讲，个人感觉动态规划可以算作是递归算法的优化，它将已经算好的数据存储在数组里，避免了递归造成的重复计算，大大减少了时间开销

教你彻底学会动态规划——入门篇-CSDN博客

（有的算法是逐步优化成这个样子的，所以可以先去学习了解一下最初时算法的样子，这样可以更方便理解）

对于本题而言，因为并不能单纯的选择较大或者较小的数，来填满箱子，于此同时，我们并不清楚最佳方案时的个数，所以很难通过暴力枚举的算法来解决

于是，我们可以简要的学习一下本题所用的动态规划的思路：

首先，设个数组，来数组的下标代表每一种空间容量，也就是从1~最大值，

然后，我们开始将物品逐个放入，在不超过背包空间容量的前提下，取最大值。

最后，做减法即可。

如果你好奇整个数组是如何变化的。

那么我们不妨尝试着把该数组输出一下：

结果如下：

14
4
3
7
5
8
1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10 ? ?11 ? ?12 ? ?13 ? ?14
0 ? ? 0 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3
0 ? ? 0 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 7 ? ? 7 ? ? 7 ? ? 10 ? ?10 ? ?10 ? ?10 ? ?10
0 ? ? 0 ? ? 3 ? ? 3 ? ? 5 ? ? 5 ? ? 7 ? ? 8 ? ? 8 ? ? 10 ? ?10 ? ?12 ? ?12 ? ?12
0 ? ? 0 ? ? 3 ? ? 3 ? ? 5 ? ? 5 ? ? 7 ? ? 8 ? ? 8 ? ? 10 ? ?11 ? ?12 ? ?13 ? ?13

我们发现，对于任意v，v[i]均小于v

参考资料

1.

C语言算法训练 - 装箱问题_动态规划问题（有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数））_有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积-CSDN博客

?2.

教你彻底学会动态规划——入门篇-CSDN博客