‘壹’ c语言：背包问题(数据结构)
详细程序代码如下:
用VC6.0编译.保存代码时,以.C为后缀名
下面是一组测试数据:
请输入背包能容纳的最大重量：20
请输入物品个数：10
请输入每一个物品的重量和价值：1,11,2,22, 3,33.....10,100
结果是正确的.
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define NUMBER 20/*最大物品数量*/
#define TRUE 1
#define FALSE 0
struct Record/*本结构体用于保存每一次结果*/
{
int totalWeight;/*本次结果的总价值*/
int goods[NUMBER];/*本次结果对应的下标*/
struct Record *next;
};
struct Record *headLink;
struct Record result;
int stack[NUMBER];
int top;
int weight[NUMBER];/*保存物品重量的数组*/
int value[NUMBER];/*保存对应（下标相同）物品的价值*/
int knapproblen(int n,int maxweight,int weight[]);
void CreateHeadLink(void);
struct Record *MallocNode(void);
void InsertOneNode(struct Record *t);
void GetResult(void);
void ShowResult(void);
void main()
{
int n,i;
int maxWeight;/*背包能容纳的最大重量*/
printf("请输入背包能容纳的最大重量：\n");
scanf("%d",&maxWeight);
printf("请输入物品个数：\n");
scanf("%d",&n);
printf("请输入每一个物品的重量和价值：\n");
for(i=0;i<n;i++)
{
printf("请输入第%d个物品重量\n",i+1);
scanf("%d",&(weight[i]));
printf("请输入第%d个物品价值\n",i+1);
scanf("%d",&(value[i]));
}
if(knapproblen(n,maxWeight,weight)==TRUE)/*调用背包处理函数，如果成功就输出“答案”*/
{
GetResult();/*遍历链表，查找最佳的结果*/
ShowResult();/*显示结果*/
}
free(headLink);
getch();
}
/*调用背包处理函数*/
int knapproblen(int n,int maxweight,int weight[])
{
struct Record *p;
int i=1,j;
int tempTop=0;
top=0;/*先赋栈指针为0*/
CreateHeadLink();/*先建立链头*/
while((maxweight>0)&&(i<=n))/*当还可以装下物品，且物品没有用完时*/
{
if((maxweight-weight[i]==0)||(maxweight-weight[i]>0)&&(i<n))/*正好装完物品或还能容纳物品且物品没有用完时*/
{
stack[++top]=i;/*把对应物品的处标保存到栈中*/
p=MallocNode();/*每一次得到一个结果后，就将该结果保存到链表中*/
for(tempTop=top,j=0;tempTop>0;tempTop--,j++)
{
p->totalWeight+=value[stack[tempTop]];/*得到本次结果的总价值*/
p->goods[j]=stack[tempTop];/*得到本次结果对应的物品下标*/
}
InsertOneNode(p);/*加到链表中*/
maxweight=maxweight-weight[i];
}
if(maxweight==0)/*能装入包中*/
{
return TRUE;
}
else if((i==n)&&(top>0))/*继续测试*/
{
i=stack[top];
top=top-1;
maxweight=maxweight+weight[i];
}
i++;
}
return FALSE;
}
/************************************
函数功能：建立链表表头
************************************/
void CreateHeadLink(void)
{
struct Record *p;
p=(struct Record*)malloc(sizeof(struct Record));
headLink=p;
p->next=NULL;
}
/************************************
函数功能：申请一个新结点，并将其初始化
************************************/
struct Record *MallocNode(void)
{
struct Record *p;
int i;
p=(struct Record*)malloc(sizeof(struct Record));
if(p==NULL)
return NULL;
p->totalWeight=0;/*初始化总价值为0*/
for(i=0;i<NUMBER;i++)
p->goods[i]=-1;/*初始化下标为-1，即无效*/
p->next=NULL;
return p;
}
/************************************
函数功能：在链表的结尾处增加一个结点
************************************/
void InsertOneNode(struct Record *t)
{
struct Record *p;
p=headLink;
while(p->next)
{
p=p->next;
}
p->next=t;
}
/************************************
函数功能：遍历链表，找总价值最大的结点保存到
result中
************************************/
void GetResult(void)
{
struct Record *p;
int i;
result.totalWeight=headLink->next->totalWeight;/*先将第一个结点当作"最佳"结果*/
for(i=0;i<NUMBER;i++)
{
if(headLink->next->goods[i]==-1)
break;
result.goods[i]=headLink->next->goods[i];
}
p=headLink->next->next;
while(p)/*查找最佳结果*/
{
if(p->totalWeight>result.totalWeight)/*如果发现p点价值比当前结果还大，则将p又作为最佳结果*/
{
result.totalWeight=p->totalWeight;
for(i=0;i<NUMBER;i++)
result.goods[i]=-1;
for(i=0;i<NUMBER;i++)
{
if(p->goods[i]==-1)
break;
result.goods[i]=p->goods[i];
}
}
p=p->next;
}
}
/***************************
显示最佳结果
*******************************/
void ShowResult(void)
{
int i;
printf("最佳装载如下：\n");
for(i=0;i<NUMBER;i++)
{
if(result.goods[i]==-1)
break;
printf("weight[%d]=%d\tvalue[%d]=%d\t",result.goods[i],weight[result.goods[i]],result.goods[i],value[result.goods[i]]);
if((i+1)%2==0)
printf("\n");
}
printf("\n总价值是：\n%d",result.totalWeight);
}
‘贰’ 求大神给一份C语言01背包的代码，要每一行都有注释，谢谢！
这是一个背包问题，该算法已经是最简单的了，还有递归算法，我觉得更麻烦。对你的代码进行解释如下：
//背包问题：有m件物品和一个承重为t的背包。第i件物品的重量是w[i]，价值是v[i]。
//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
#include<stdio.h>
#include<conio.h>
#include<string.h>
intf[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值
intmax(intx,inty){//返回x,y的最大值
if(x>y)returnx;
returny;
}
intmain(){
intt,m,i,j;
memset(f,0,sizeof(f));//总价值初始化为0
scanf("%d%d",&t,&m);//输入背包承重量t、物品的数目m
for(i=1;i<=m;i++)
scanf("%d%d",&w[i],&v[i]);//输入m组物品的重量w[i]和价值v[i]
for(i=1;i<=m;i++){//尝试放置每一个物品
for(j=t;j>=w[i];j--){
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
}
}
printf("%d",f[t]);//输出承重量为t的背包的总价值
printf(" ");
getch();
return0;
}
‘叁’ c语言背包问题，求高手解答
对01背包求解，方法有回溯法、分支限界法、动态规划法等。给你一个较容易理解的解法：穷举搜索。问题求解的结果实际上是一个01序列，0表示该物品未装入背包，1表示装入背包。以本题为例，设求解结果为0111011，表示第0个和第4个未装入，其他均装入。关键就是如何找到这个01序列。设物品数量为n，则解空间为2^n，所以穷举搜索的时间效率为O(2^n)。
#include <stdio.h>
#define N 7
int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30};
char name[] = "ABCDEFG";
int max = 0, Max[N]; /*max用于存放最大价值，Max用于存放最优解向量*/
int v[N]; /*v：求解时用于存放求解过程向量*/
template <class T>
void Swap(T &a, T &b)
{
T tmp = a;
a = b, b = tmp;
}
void Knapsack(int step, int bag, int value1, int value2, int n)
/*step表示第step步的选择（即第step个物品的选择），bag为背包剩余容量，value1表示包中现有物品总价值，value2表示剩余物品总价值，n为物品总数量*/
{
int i;
if((step >= n) || (weight[step] > bag) || (value1 + value2 <= max)) /*如果所有物品都选择完毕或剩余的物品都放不进或者包中物品总价值与剩余物品总价值之和小于等于目前的已知解，则找到一个解(但不一定是最终解或更优解)*/
{
for(i = step; i < n; i++) v[i] = 0; /*剩余的物品都不放入*/
if(value1 > max) /*如果本次求得的解比以往的解更优，则将本次解作为更优解*/
{
max = value1;
for(i = 0; i < n; i++) Max[i] = v[i]; /*将更优解保存到Max向量中*/
}
return;
}
v[step] = 0, Knapsack(step + 1, bag, value1, value2 - cost[step], n); /*不将第step个物品放入背包，第step个物品的价值被放弃，进行下一步的选择*/
v[step] = 1, Knapsack(step + 1, bag - weight[step], value1 + cost[step], value2 - cost[step], n); /*将第step个物品放入背包，进行下一步的选择*/
}
void main( )
{
/*输入数据：背包容量、物品数量、重量、价值 代码略*/
int bag = 150, i, j, min, totalcost;
/*按物品重量从小到大的顺序对物品排序，排序时cost向量中的相对顺序也要作相应移动*/
for(i = 0; i < N - 1; i++) {
for(min = i, j = i + 1; j < N; j++)
if(weight[j] < weight[min]) min = j;
if(i != min) {
Swap(weight[i], weight[min]);
Swap(cost[i], cost[min]);
Swap(name[i], name[min]);
}
}
for(totalcost = 0, i = 0; i < N; i++) totalcost += cost[i]; /*求总价值*/
Knapsack(0, bag, 0, totalcost, N); /*bag为空背包容量, totalcost为物品总价值, N为物品数量*/
/*以下输出解*/
printf("最大价值为: %d。\n装入背包的物品依次为：\n", max);
for(i = 0; i < N; i++)
if(Max[i]) printf("%c\t", name[i]);
printf("\n");
}
我的回答你满意吗？如果满意，就请采纳哦，或者你也可以继续追问。
‘肆’ 背包问题C语言简短代码，大神们最好带解释和注释，谢谢！！！
不知道你说的哪种类型的背包，我就说下最简单的吧。
一、01背包
问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
（1）基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
意思简要来说就是：如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
（2）优化空间复杂度：以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符。
（3）初始化的细节问题：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
【写的伪代码，能看懂哈。。。不懂再问好了】