Question

背包问题(C语言)

有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
请用C语言编程
也可以用动态规划
(2)数字1～n的全排列（不重复）

Answer 1

我copy一下别人的递归算法，假如你有时间限时的话，那我就用动态规划帮你重新code一个

#include <stdio.h>
#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了
int n;//物品总种数
double limitW;//限制的总重量
double totV;//全部物品的总价值
double maxv;//解的总价值
int option[N];//解的选择
int cop[N];//当前解的选择
struct {//物品结构
double weight;
double value;
}a[N];
//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值
void find(int i,double tw,double tv)
{
int k;
//物品i包含在当前方案的可能性
if(tw+a[i].weight <= limitW){
cop[i]=1;
if(i<n-1)find(i+1,tw+a[i].weight,tv);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在当前方案的可能性
if(tv-a[i].value>maxv){
if(i<n-1)find(i+1,tw,tv-a[i].value);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
void main()
{
int k;
double w,v;
printf("输入物品种数:");
scanf("%d",&n);
printf("输入各物品的重量和价值:");
for(totV=0.0,k=0;k<n;++k){
scanf("%lf %lf",&w,&v);
a[k].weight = w;a[k].value = v;
totV += v;
}
printf("输入限制重量:");
scanf("%lf",&limitW);
maxv=0.0;
for(k=0;k<n;++k)cop[k]=0;
find(0,0.0,totV);
for(k=0;k<n;++k)
if(option[k])printf("%4d",k+1);
printf("总价值为: %2f",maxv);
}

Answer 2

#include <stdio.h> 
#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了 
int n;//物品总种数 
double limitW;//限制的总重量 
double totV;//全部物品的总价值 
double maxv;//解的总价值 
double maxw=0.0;//解的总重量-------------->新加
int option[N];//解的选择 
int cop[N];//当前解的选择 
struct {//物品结构 
double weight; 
double value; 
}a[N]; 
//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值 
void find(int i,double tw,double tv) 
{ 
int k; 
//物品i包含在当前方案的可能性 
if(tw+a[i].weight <= limitW){ 
cop[i]=1; 
if(i<n-1)find(i+1,tw+a[i].weight,tv); 
else{ 
for(k=0;k<n;++k) 
option[k]=cop[k]; 
maxv=tv; 
} 
} 
cop[i]=0; 
//物品i不包含在当前方案的可能性 
if(tv-a[i].value>maxv){ 
if(i<n-1)find(i+1,tw,tv-a[i].value); 
else{ 
for(k=0;k<n;++k) 
option[k]=cop[k]; 
maxv=tv-a[i].value; 
} 
} 
} 
void main() 
{ 
int k; 
double w,v; 
printf("输入物品种数:"); 
scanf("%d",&n); 
printf("输入各物品的重量和价值:"); 
for(totV=0.0,k=0;k<n;++k){ 
scanf("%lf %lf",&w,&v); 
a[k].weight = w;a[k].value = v; 
totV += v; 
} 
printf("输入限制重量:"); 
scanf("%lf",&limitW); 
maxv=0.0; 
for(k=0;k<n;++k)cop[k]=0; 
find(0,0.0,totV); 
for(k=0;k<n;++k) 
if(option[k])
{//-------------->新加
maxw+=a[k].weight//-------------->新加
printf("%4d",k+1); 
}//-------------->新加
printf("总价值为: %2f",maxv); 
printf("总重量为: %2f",maxw); //-------------->新加
}提问者评价

Answer 3

下面是核心的代码(递归函数的代码)
别的由你自己搞掂啦(在main函数中的实现,输入,输出的格式)
s 为一个背包可以放入的物品总重量.n为物品数,w[n]为物品重量的数组.
int knap(int s,int n)
{if(s==0)
return (1);
else if((s<0)||((s>0)&&(n<1))
return(0);
else if(knap(s-w[n-1],n-1)==1)
{printf("result:n=%d,w[%d]=%d \n",n,n-1,w[n-1]);
return(1);
}
else
return(knap(s,n-1));
}

因为其满足一个条件
1 if(s==0)
knap(s,n)= 0 if(s<0)
0 if(s>0&&n<1)
knap(s,n-1) or knap(s-w[n],n-1)

值为0或1时是函数递归的出口.
我是按书上打上去的,打错了请见谅啦.
你慢慢体会一下个中原理.

Answer 4

/*（背包问题2）：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的
选择方案，使选中的物品之总重量不超过指定的限制重量s，而选中物品的价值之和最大*/

#include<iostream.h>

double knap(double p[], double w[], double s, int n) {
if (!n) return 0;
double r1 = 0, r2;
if (s >= w[n-1])
r1 = knap(p, w, s-w[n-1], n-1) + p[n-1];
r2 = knap(p, w, s, n-1);
return r1 > r2 ? r1 : r2;
}

void print(double p[], double w[], double s, int n, double &sp, double &sw) {
if (!n) return;
if (s >= w[n-1] && knap(p, w, s-w[n-1], n-1) + p[n-1] > knap(p, w, s, n-1)) {
sp += p[n-1]; sw += w[n-1];
print(p, w, s-w[n-1], n-1, sp, sw);
cout<<"第"<<n<<"件物品(值:"<<p[n-1]<<", 重:"<<w[n-1]<<")\n";
}
else print(p, w, s, n-1, sp, sw);
}

void main() {
cout<<"（背包问题2）：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的\n"
"选择方案，使选中的物品之总重量不超过指定的限制重量s，而选中物品的价值之和最大\n";
double s, *p, *w, sp = 0, sw = 0;
int i, n;
cout<<"\n输入背包能装载的重量s与物品件数n:";
cin>>s>>n;
p = new double[n];
w = new double[n];
cout<<endl;
for (i = 0; i < n; i++) {
cout<<"输入第"<<i+1<<"件物品的价值与重量:";
cin>>p[i]>>w[i];
}
cout<<"\n背包问题2: \n背包能装载的重量s = "<<s<<endl;
for (i = 0; i < n; i++)
cout<<"第"<<i+1<<"件物品值:"<<p[i]<<", 重:"<<w[i]<<endl;
cout<<"\n选出的物品如下:\n";
print(p, w, s, n, sp, sw);
cout<<"选出的物品总价值为:"<<sp<<" 总重量为:"<<sw<<endl;
}

Answer 5

http://zhidao.baidu.com/question/9106737.html?fr=qrl3