算法装载问题
⑴ 装载问题的贪心选择性质如何证明
设箱子重量从小到大（x1,x2,...,xn），若集合A是最优装载问题的一个最优解。A中第一个箱子为k。若k=1，A就是一个满足贪心性质的最优解。假如当k>1，令B=A-{k}+{1},因为Wk>=W1,则B中的总重量小于等于A中的总重量，A是最优解，则B也是最优解，而B是选择以箱子1为开始的最优解。可知总存在以贪心选择开始的最优解。
⑵ 算法的相关
经典的算法有很多，如欧几里德算法，割圆术，秦九韶算法。
随着计算机的发展，算法在计算机方面已有广泛的发展及应用，如用随机森林算法，来进行头部姿势的估计，用遗传算法来解决弹药装载问题，信息加密算法在网络传输中的应用，并行算法在数据挖掘中的应用等。
⑶ 装载问题 PASCAL 高手来帮帮
我看的没错的话，你这个程序用的搜索，时间复杂度为（2^n),n只要到16你的程序准超时。所以搜索不是这个题的最优算法。这个题的最优算法是DP。很明显是个背包问题，我直接给你DP方程,你用2个for循环OK。
f[i,j]=max(f[i-1,j],f[i-1,j-w[i]]+1);
程序再怎么剪枝也没用啊，我如果n=31，就有2*10^9中可能，搜索肯定过不了，这个题就是动态规划，你从网上查一下DD牛的背包九讲。这个题属于第一个类型。
好吧……我错了……我不是很擅长剪枝。
价值怎么不是1？他要求的是最大的集装箱数目。那每装上一个，自然价值+1，你加个w[i]算什么？你的方程含义是在不超过最大容量的情况下，最多装的重量为多少。显然不对。
⑷ 我也想要算法设计与分析的习题答案，只要回溯法的装载问题改进程序那两个，帮个忙啊
这个应该不错
var a:array[0..11] of integer;
n,k,t:integer;
procere p(k:integer);
var i,j:integer;
g:boolean;
begin
if k>n then begin
for i:=1 to n-1 do
write(a[i],' ');
writeln(a[n]);
t:=t+1;
end
else begin
for i:=1 to n do begin
g:=true;
for j:=1 to k-1 do
if (i=a[j]) or (abs(i-a[j])=abs(k-j)) then g:=false;
if g then
begin
a[k]:=i;
p(k+1);
end;
end;
end;
end;
begin
readln(n);
t:=0;
k:=1;
p(k);
if t=0 then writeln('no solute!');
if t>0 then writeln(t);
end.
⑸ 算法 C++ 装载问题 分支定界
不会，非最优解不会包含最优解，如果包含了，这就是一个更优的解。
⑹ 跪求算法!!!!!!!!!!!!
最有装载问题?
网络.
⑺ 关于装载问题的C++
将MaxLoading(*w,c,n,*bestx); 修改为：
MaxLoading(w,c,n,bestx);
就可以了
另外，你这个程序估计你敲错的太多了
我修改后，可以编译过，也许有其他逻辑错误：
#include <conio.h>
#include <iomanip.h>
#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
template<class Type>
class Loading
{
friend Type MaxLoading(Type[],Type,int,int[]);
private:
void Backtrack(int i);
int n,*x,*bestx;
Type*w,c,cw,bestw,r;
};
template<class Type>
void Loading<Type>::Backtrack(int i)
{
if(i>n-1)
{
if(cw>bestw)
{
for(int j=0;j<=n-1;j++)
{
bestx[j]=x[j];
bestw=cw;
}
return;
}
r-=w[i];
if(cw+w[i]<=c)
{
x[i]=1;
cw+=w[i];
Backtrack(i+1);
cw-=w[i];
}
if(cw+r>bestw)
{
x[i]=0;
Backtrack(i+1);
}
r+=w[i];
}
}
template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
Loading<Type>X;
X.x=new int[n+1];
X.w=w;
X.c=c;
X.n=n;
X.bestx=bestx;
X.bestw=0;
X.cw=0;
X.r=0;
for(int i=1;i<=n;i++)
X.r+=w[i];
X.Backtrack(1);
delete[]X.x;
return X.bestw;
}
void main()
{
int c,n,*w,*bestx,i;
cout<<"输入轮船的重量:"<<endl;
cin>>c;
cout<<endl;
cout<<"输入货箱个数:";
cin>>n;
cout<<endl;
w=new int[n];
bestx=new int[n];
cout<<"请输入"<<n<<"货箱重量:";
for(i=0;i<n;i++)
{
cin>>*(w+i);
}
for(i=0;i<n;i++)
{
*(bestx+i)=0;
}
MaxLoading(w,c,n,bestx);
}
⑻ 贪心算法的最优装载问题
void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)
1.void loading(int W[],int X[],int c,int n)
2.没有定义i;
3.for（;;）是冒号，非逗号
⑼ C语言关于装载问题（背包问题）的一个程序 我写的程序输出不满足题意 但我检查不出来错误 希望大神解决
想法:是先让c1船尽量装货物是可以的，但是算法应该不对，可以用下面的算法
// 前k个数中去任意个数，且这些数之和为s的取法是否存在
int main()
{
int n, i, k1, k2, s, u;
cin >> n;
for (i=1; i<=2*n; i++)
cin >> A[i];
int sum = 0;
for (i=1; i<=2*n; i++)
sum += A[i];
memset(dp,0,sizeof(dp));
dp[0][0]=true;
// 外阶段k1表示第k1个数，内阶段k2表示选取数的个数
for (k1=1; k1<=2*n; k1++) // 外阶段k1
{
for (k2=k1; k2>=1; k2--) // 内阶段k2
for (s=1; s<=sum/2; s++) // 状态s
{
//dp[k1][s] = dp[k1-1][s];
// 有两个决策包含或不包含元素k1
if (s>=A[k1] && dp[k2-1][s-A[k1]])
dp[k2][s] = true;
}
}
// 之前的dp[k][s]表示从前k个数中取任意k个数，经过下面的步骤后
// 即表示从前k个数中取任意个数
for (k1=2; k1<=2*n; k1++)
for (s=1; s<=sum/2; s++)
if (dp[k1-1][s]) dp[k1][s]=true;
// 确定最接近的给定值sum/2的和
for (s=sum/2; s>=1 && !dp[2*n][s]; s--);
}
⑽ 如何证明最优装载问题具有贪心选择性质
设某种货币系统为(1,5,10,25)四种币值(单位:元)，要用最少的币数找出 n元钱，
问:能否用贪心算法进行求解，并证明。(不要求写算法) 参考解答:贪心性质(最大面额优先选最多)证明:
对 n<=25的情况，易由穷举得证。
当 n>25时，设 n=1*a1+5*a2+10*a3+25*a4
为了使 a1+a2+a3+a4最小，易知:
a1<5，若 a1>=5，可将 5个 1元兑换为 1个 5元，币数减少。
a2<2，若 a2>=2，可将 2个 5元兑换为 1个 10元，币数减少。
当 a2=0时，a3<3，若 a3>=3，可将 3个 10元兑换为 1个 5元和 1个 25元，币数减 少。
当 a2>0时，a3<2，若 a2>=2，可将 1个 5元和 2个 10元兑换为 1个 25元，币数减 少。
即，为了使 a1+a2+a3+a4最小，所使用的 1、5、10元币的币数的上限为: a1=4,a2=0,a3=2或 a1=4,a2=1,a3=1
则所使用的 1、5、10元币的币值上限为:
4*1+0*5+2*10=24或 4*1+1*5+1*10=19
均不超过 25，因此，为了使 a1+a2+a3+a4最小，应使 a4达到最大。贪心选择性质得 证。
最优子结构性质证明:
当 a4的值确定后，为了使 a1+a2+a3+a4达到最小，须使 a1+a2+a3达到最小，仍为同 型的最优问题。