题目描述
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入
第一行为一个整数，表示箱子容量；
第二行为一个整数，表示有n个物品；
接下来n行，每行一个整数表示这n个物品的各自体积。
输出
一个整数，表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0
- 这个题目运用到了dp（动态规划）。
- 我们首先需要开辟一个大小比v大一点的数组dp，这个数组用来模拟放置物品。
- 我们每一次得到要放进去的容量，从dp数组最后一个下标就也是v开始模拟，也就是j=v,是v是因为，我们最多放置v那么大的容量。
- 然后往前推算，这个box[i]到底放不放。推算结束条件是什么？就是我们前一次放的那个下标不能是小于0的，也就是j>=box[i]
- 前一次记录结果是存在dp[j-box[i]]中的（如果我们要拿这个box[i]，我们就得看当容量为dp[j-box[i]]时取得的最优解），如果这个值加上box[i]的值，那么我就就拿这个box[i]，否则就保持原来的值（就是一个拿和不拿问题）。
- 在我们重复5这个动作的时候，我们最终能保证dp[v]就是最大能拿的容量，那么v-dp[v]就是最小剩余的容量。
代码如下：
#include<stdio.h>
int dp[20005];//表示容积为v时可放置物品的容量
int max(int a,int b)
{
if(a>=b) return a;
return b;
}
int main()
{
int v,n,i,j;
scanf("%d%d",&v,&n);
int box[40] = {0};
for(i = 0;i<n;i++)
{
scanf("%d",&box[i]);
}
for(i = 0;i < n; i++)
{
//每一个试着判断放进去
for(j = v ;j >= box[i]; j--)
{
dp[j] = max(dp[j],dp[j-box[i]] + box[i]);//每次贪心放不放下这个box[i],每次都要保证时最优解，也就是最大能拿的。
//每次都从v往前面贪心，j-box[i]是在查看如果我们要放进去，那么剩下的容量的最优解
//如果放进去比本来大，就放进去，否则不放
}
}
printf("%d",v-dp[v]);//dp[v]这个元素会记下最终贪心的结果
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
