这道题看似是搜索,但是可以用背包做。
题目要求求出最小的剩余空间,也就是要求出最大的可装重量
这样,我们可以将一个物体的重量当作它的价值,进而将题目转变为一个基本的01背包问题:
有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)和一个价值(等于体积)。
要求n个物品中,任取若干个装入箱内,使总价值最大。
对于每一个物体,都有两种状态:装 与不装
那么,对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )(w为重量(即价值))
其中,f ( m - w[i] ) 指在装了物品i后,箱子的剩余容量能装的最大重量
f ( m - w[i] ) + w[i] 指在在装了物品i后,箱子能装的最大重量
程序如下:
#include<cstdio>
using namespace std;
int m,n;//m即箱子容量V
int f[20010];
int w[40];
int main()
{
int i,j;
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(i=1;i<=n;i++)
{
for(j=m;j>=w[i];j--)
{ //注意:这里必须是从m到w[i],否则一个物体会被多次装入箱子,见例1
if(f[j]<f[j-w[i]]+w[i])
{
f[j]=f[j-w[i]]+w[i];
}
}
}
printf("%d\n",m-f[m]);
}
0.0分
2 人评分
C二级辅导-计负均正 (C语言代码)浏览:698 |
C语言训练-大、小写问题 (C语言代码)浏览:2420 |
C语言训练-排序问题<2> (C++代码)浏览:933 |
简单的a+b (C语言代码)浏览:563 |
小明A+B (C语言代码)浏览:1310 |
字符串的输入输出处理 (C语言代码)浏览:1015 |
三角形 (C++代码)记忆化搜索浏览:1316 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:685 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:891 |
IP判断 (C语言描述,蓝桥杯)浏览:1118 |