这道题看似是搜索,但是可以用背包做。
题目要求求出最小的剩余空间,也就是要求出最大的可装重量
这样,我们可以将一个物体的重量当作它的价值,进而将题目转变为一个基本的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 人评分
点我有惊喜!你懂得!浏览:1413 |
点我有惊喜!你懂得!浏览:1461 |
C二级辅导-同因查找 (C语言代码)浏览:703 |
2005年春浙江省计算机等级考试二级C 编程题(3) (C语言代码)浏览:415 |
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:689 |
c primer plus 第十二章 12.1小节浏览:399 |
【亲和数】 (C语言代码)浏览:541 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:899 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:590 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1334 |