杭州交通信息网成都沙湾路小学地址:求动态规划 装箱问题
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/28 15:41:10
1．输入物品体积v和物品数n；
2．输入n个物品的体积w[1]至w[n]；
3．s[0,1..v]←false;{使用前0个物品，体积和1至v不能得到}
4．s[0,0]←true;{使用前0个物品，体积和0能得到}
5．for i←1 to n do{求前i个物品中选取若干，能否得到体积和k}
6． for k←v downto 0 do{也可0 to v}
7． If (k≥w[i]) and (s[i-1,k-w[i]]) then
{体积k>=物品i的体积 且 前i-1个物品能得到体积和k-w[i]}
8． s[i,k]←true{前i个物品能得到体积和k}
9． else
10． s[i,k]←s[i-1,k];{前i个物品能得否到体积和k取决于前i-1个物品能得否到体积和k}
11．从v至0顺序查找使用前n个物品能得到的最大体积k；
12．输出最小剩余空间v-k；
这是算法，但我不知道第11步？？？？？？zhe么打啊
2．输入n个物品的体积w[1]至w[n]；
3．s[0,1..v]←false;{使用前0个物品，体积和1至v不能得到}
4．s[0,0]←true;{使用前0个物品，体积和0能得到}
5．for i←1 to n do{求前i个物品中选取若干，能否得到体积和k}
6． for k←v downto 0 do{也可0 to v}
7． If (k≥w[i]) and (s[i-1,k-w[i]]) then
{体积k>=物品i的体积 且 前i-1个物品能得到体积和k-w[i]}
8． s[i,k]←true{前i个物品能得到体积和k}
9． else
10． s[i,k]←s[i-1,k];{前i个物品能得否到体积和k取决于前i-1个物品能得否到体积和k}
11．从v至0顺序查找使用前n个物品能得到的最大体积k；
12．输出最小剩余空间v-k；
这是算法，但我不知道第11步？？？？？？zhe么打啊
这是个较经典的动态规划问题。
思想是：因为题目要求在所有大小的货物里找一些装进箱子，并使其所装的货物量
最大，穷举的话必然超时，我们利用动态规划，用数组标记记住所有货物的部分和
，每次读进一个数，就是利用原来的结果，在任意增加一个数据的情况下，都能算
出所有数据里所有任意组合的部分和，有点像“厚古薄今”的思想。说了一大堆废
话，我们看下面的算法：
#include<stdio.h>
#include<string.h>
int main()
{
int cases[21000],n,i,maxval,now,j;
while(scanf("%d",&maxval)!=EOF) //maxval为最大容量
{
memset(cases,0,sizeof(cases)); //置0
cases[0]=1;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&now);
for(j=maxval;j>=0;j--)
if(cases[j] && j+now <= maxval) cases[j+now]=1;
}
for(i=maxval;i>=1 && !cases[i];i--);
printf("%d\n",maxval-i);
}
return 0;
}