Question

分布估计算法求解0-1背包问题算法的C语言程序；

背包问题描述

现有n种物品，对，已知第i种物品的重量为正整数，价值为正整数，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。对每种物品只有两种选择，可以选择放与不放。即当物件被选入背包时，定义变量=1，否则=0。

Answer 1

思路是：
1、先将所有东西按价值和重量的比值（价重比）从大到小排列。这里我用的冒泡排序。
2、将价重比大的先放到背包里。直到背包不能再放为止。此时价格就是最大的。

你应该能看懂。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LIMIT 100
#define TN 20

typedef struct{
int weight; //东西的重量
int value; // 东西的价值
int selected; // 是否放进去
}Things;

void swap_things(Things *t1, Things *t2) // 只是一个交换函数而已。
{
int weight, value, selected;
weight=t1->weight;
value=t1->value;
selected=t1->selected;
t1->weight=t2->weight;
t1->value=t2->value;
t1->selected=t2->selected;
t2->weight=weight;
t2->value=value;
t2->selected=selected;
}

void sort_things(Things t[], int n) // 排序函数，按照价重比排序（价格与重量的比值）
{
int i,j;
double vpw1=0, vpw2=0;
for(i=0;i<n-1;i++)
{
for(j=n-1;j>i;j--)
{
vpw1=(double)t[j].value/t[j].weight; //求出第 j 个东西的价重比
vpw2=(double)t[j-1].value/t[j-1].weight; // 求出第j-1个东西的价重比
if(vpw1>vpw2) // 如果第 j 个的价重比大于 第 j-1个价重比，则将这两个东西的位置调换一下。
swap_things(&t[j],&t[j-1]);
}
}
}

void select_things(Things t[], int n, int limit) // 这个函数用来选择要放进去的东西
{
int w=0, v=0,i;
for(i=0;i<n;i++)
{
if(w+t[i].weight>limit) // 如果目前所有放进去的东西的重量大于限制的重量，就不放东西了
break;
w+=t[i].weight; // 计算目前所有放进去的东西的重量
v+=t[i].value; // 计算目前所有放进去的东西的价格
t[i].selected=1; // 把这个东西标记为放进去了
}
printf("totel: weight=%d, value=%d\n",w,v); // 打印放进去的东西的总重量和总价格
}

int main(void)
{
Things t[TN];
int i;
srand((unsigned)time(NULL));
for(i=0;i<TN;i++) // 初始化所有的东西的重量和价格
{
t[i].weight=rand()%TN+1;
t[i].value=rand()%TN+1;
t[i].selected=0;
}

sort_things(t,TN);
select_things(t,TN,LIMIT);
printf("weight\tvalue\tselected\n");
for(i=0;i<TN;i++) // 打印所有东西的重量、价格和是否放进去。
printf("%d\t%d\t%d\n",t[i].weight,t[i].value,t[i].selected);

return 0;
}

Answer 2

#include<iostream>
#include<string>
using namespace std;
int mVal,nVal;
int sum;
int *pOut;
void calFun(int m,int n)
{
if(m<1||n<1||(n==1&&m!=1))
return;
if(m==n)
{
pOut[n]=1;
for(int i=1;i<nVal;i++)
{
if(pOut[i])
cout<<i<<" ";
}
cout<<endl;
pOut[n]=0;
++sum;
}
calFun(m,n-1);
pOut[n]=1;
calFun(m-n,n-1);
pOut[n]=0;
}
int main(int argc,char *argv[])
{
cout<<"m:";
cin>>mVal;
cout<<"n:";
cin>>nVal;
if(mVal<nVal) nVal=mVal;
pOut=new int[nVal+1];
memset(pOut,0,(nVal+1)*sizeof(int));
calFun(mVal,nVal);
cout<<"总数:"<<sum<<endl;
delete []pOut;
return 0;
}

追问

这是用分布估计算法写出的程序吗？