背包问题(C语言)

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

#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不包含在当前方案的可能性