装箱问题（背包问题）

题目描述

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

输入格式

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

输出格式

一个整数，表示箱子剩余空间。

样例输入

24
6
8
3
12
7
9
7

样例输出

0

解题思路

这一题乍一看与背包问题相似，但是相较于背包问题更加简单，没有价值设定，一开始我试着用更加通俗易懂的方法写，即从大到小依次遍历，进行装箱，直到装不下为止

我用了两个for循环以求left（剩余空间大小），即

//第一个for循环遍历到 装入下一个箱子，空间为负为止
for(int i=0;i<n;i++)//将箱子从大到小依次装到箱中{if(arr[i]+sum<v){sum+=arr[i];}}left=v-sum;//这里空间剩余：3
for(int i=0;i<n;i++)
{if(arr[i]<=left)//以剩余空间作为判断条件    {         sum+=arr[i];left=v-sum;//更新left}
}

最终代码得 

#include<stdio.h>int main()
{int v, n;//v表示体积，n表示物品个数int max, temp,sum=0,left;scanf("%d", &v);scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++){scanf("%d", &arr[i]);}for (int i = 0; i < n; i++)//冒泡排序,将体积从大到小放入arr[i]中{for(int j=0;j < n-1-i;j++){if (arr[j + 1] > arr[j]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
/*for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
*/for(int i=0;i<n;i++)//将箱子从大到小依次装到箱中{if(arr[i]+sum<v){sum+=arr[i];}}left=v-sum;//这里空间剩余：3for(int i=0;i<n;i++){if(arr[i]<=left)//以剩余空间作为判断条件sum+=arr[i];left=v-sum;}printf("%d",left);return 0;
}

但这样写不具有通用性，还是要用到动态规划算法，代码如下

其中最重要的一段即

 for(i=1;i<=n;i++)
//从1开始是因为当v=0, 箱子装不下任何东西，i=0表示第0件物品，即没有物品，所以跳过 for(j=v;j>=1;j--)
/*
把数组压缩到一维必须逆序，因为01背包问题就是由旧值推新值，从前面开始的话，旧值就会过早被新值覆盖 
例如：
如果a[30]在a[20]的基础上加了w[i]=10，表示30容量这个背包它拿了w[i]=10这个东西了，但是--它没有考虑：a[20]里面是否拿过w[i]=10这个东西，所以要j--;
也就是说箱子的体积从小到大遍历，物品从大到小开始装，这样才能避免重复装入物品
*/{//j可以看作箱子当前的容量 if(w[i]<=j)//判断是否能装下物品i a[j]=MAX(a[j],a[j-w[i]]+w[i]);//原式为a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) }

for(j=v;j>=1;j--)

还是不懂为什么j--

那么就多写：

for(j=v;j>=1;j--)的情况

 for(j=1;j<=v;j++)的情况

 可以看到从a[14]开始，旧值已经覆盖新值了

注：a[j]为没放入，a[j-w[i]]+w[i]为放入
如下图所示a[j]为V(容量)，a[j-w[i]]为放入w[i]后剩余的容量，a[j-w[i]]+w[i]为放入w[i]后的容量大小，不理解的可以依据上图观察规律：

最终代码如下 

#include<stdio.h>int w[40]={0};//注意初始化 ,这里表示物品的体积
int a[30011]={0};//这里表示v
int MAX(int n,int m)
{if(m<=n) return n;else return m;
}
int main()
{int n,i,j,v;scanf("%d",&v); scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&w[i]);for(i=1;i<=n;i++)//从1开始是因为当v=0, 箱子装不下任何东西，i=0表示第0件物品，即没有物品，所以跳过 for(j=v;j>=1;j--)
/*
把数组压缩到一维必须逆序，因为01背包问题就是由旧值推新值，从前面开始的话，旧值就会过早被新值覆盖 
例如：
如果a[30]在a[20]的基础上加了w[i]=10，表示30容量这个背包它拿了w[i]=10这个东西了，但是--它没有考虑：a[20]里面是否拿过w[i]=10这个东西，所以要j--;
也就是说箱子的体积从小到大遍历，物品从大到小开始装，这样才能避免重复装入物品
*/{//j可以看作箱子当前的容量 if(w[i]<=j)//判断是否能装下物品i a[j]=MAX(a[j],a[j-w[i]]+w[i]);//原式为a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) }// a[j]为不拿，a[j-w[i]]+w[i]为拿//a[j-w[i]]+w[i]意为放入物品i后，总占用空间=物品i所占的空间+箱子剩余的空间 j-w[i] 所能被占用的最大空间 a[j-w[i]]printf("%d",v-a[v]);//此时的a[v]表示当容量为v时，箱子已被占用空间a[v] return 0;
}

这是@佳佳佳佳佳博主的图，有助于理解 

MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) 

这是最简单的背包问题，一定要理解，如果还有点迷糊的话，可以看看这篇文章

http://t.csdn.cn/X7GLD

或者

http://t.csdn.cn/CleVM