这道题看似是搜索,但是可以用背包做。
题目要求求出最小的剩余空间,也就是要求出最大的可装重量
这样,我们可以将一个物体的重量当作它的价值,进而将题目转变为一个基本的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语言程序设计教程(第三版)课后习题8.9 (Java代码)浏览:1413 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:1090 |
C语言训练-大、小写问题 (C语言代码)浏览:792 |
printf基础练习2 (C语言代码)浏览:691 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:628 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)from DQM浏览:773 |
1009题解浏览:802 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:537 |
1126题解浏览:649 |
图形输出 (C语言代码)浏览:1422 |