C语言：背包问题(数据结构)

来源：百度知道 编辑：UC知道 时间：2024/05/25 07:52:19
在背包问题中，需对容量为s 的背包进行装载。从n 个物品中选取装入背包的物品，物品i 的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。请找出背包问题的一个求解方案。
请利用动态规划，写出完整的程序（最好附有文字说明）。谢谢，这是一个project，希望程序越详细越好，考虑得越完整越好。满意的有追加！！！
一楼的麻烦看清楚题目，每个物品都有其重量和价值，要在重量允许范围内达到最大价值

详细程序代码如下:
用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("请输入背包能容纳的最大重量：&