当前位置:首页 » 编程语言 » c语言背包问题
扩展阅读
webinf下怎么引入js 2023-08-31 21:54:13
堡垒机怎么打开web 2023-08-31 21:54:11

c语言背包问题

发布时间: 2022-01-22 15:05:05

c语言 背包问题 递归算法

if(n==0)应该改成

if(n<0)才对,表示没有物品可选了。我的一个改进,但输出选择项还是有问题!

#include<stdio.h>
#include<conio.h>
#defineN3
intMaxW(intn,intC,int*Volume,int*Weight,int*Select){
intW=0,W1=0;
if(n<0){//没有物品了
return0;
}
W=MaxW(n-1,C,Volume,Weight,Select);//没放入n之前的重量
if(C>=Volume[n]){//背包剩余空间可以放下物品n
W1=MaxW(n-1,C-Volume[n],Volume,Weight,Select)+Weight[n];//放入n所能得到的重量
Select[n]=0;
if(W1>W){//放入n能获得更大的重量
Select[n]=1;
W=W1;
}
}
returnW;
}

intmain(){
intC=8,W,i;
//intVolume[N]={1,2,3,4,5};//物品体积
//intWeight[N]={1,2,5,7,8};//物品重量
intVolume[N]={2,3,5};//物品体积
intWeight[N]={5,8,7};//物品重量
intSelect[N]={0};//选择标记
W=MaxW(N-1,C,Volume,Weight,Select);
printf("MaxWeight=%d,SelectList[index(volume,weight)]: ",W);
for(i=0;i<N;++i){
if(Select[i]){
printf("%d(%d,%d)",i,Volume[i],Weight[i]);
}
}
printf(" Finished! ");
getch();
return0;
}

其中的Select数组还是会多选了,你看看。

❷ C语言背包问题递归算法

你学过数据结构了吗?如果学过,那就比较好理解,该算法的思路和求二叉树的高度的算法的思路是十分类似的。把取这i个物体看成i个阶段,则该二叉树有i+1层。其中空背包时为根结点,左孩子则为放弃了第1个物品后的背包,右孩子为选取了第1个物品后的背包。今后在对第i个物品进行选择时,向左表示放弃,向右表示选取。则递归算法可如下:
int fun(int s, int i, int n) //s传入的是背包容量, i是进行第i个物品的选取,n为剩余物品的件数
{
if(s == 0) return 有解;
else if(剩余的每件物品都装不进|| n == 0) return 无解;
L = fun(s, i + 1, n - 1); //放弃第i个物品,则下一步的背包容量仍为s,然后看其是否有解,(递归调用进入左子树)
R = fun(s - wi, i + 1, n - 1); //选取第i个物品,则下一步的背包容量为s-wi,然后看其是否有解,(递归调用进入右子树)
return (l, r); //综合考虑左右两边,看哪边是正解或都无解。其实应该返回 return (L||R);
}

❸ C语言动态规划之背包问题求解

#include<stdio.h>
int max(int a,int b)
{
if (a>b) return a;
else return b;
}
int main()
{
//int max(int , int );
int n,m,i,j;
int data[101][2];
int f[101][101];
scanf("%d%d",&n,&m); //n表示个数,m表示能背的最大重量
for(i=1;i<=n;i++)
{
scanf("%d%d",&data[i][0],&data[i][1]);
} //我是数组从第一个开始记得,看着容易理解,没必要去省那么几B的内存
for(i=0;i<=m;i++) f[0][i]=0;
for(i=0;i<=n;i++) f[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
f[i][j]=0;
if (j>=data[i][0])
{
f[i][j]=max(f[i-1][j],f[i-1][j-data[i][0]]+data[i][1]);
//对于这件物品要么不选要么选,不选是f[i-1][j];
//选的话为f[i-1][j-data[i][0]]此处j-data[i][0]是因为要选上一次就得少背j-data[i][0]的重量
//才能装下这次的物品
}
else f[i][j]=f[i-1][j];
}
printf("%d\n",f[n][m]);
return 0;
}
然后常见的背包问题还有多重背包问题,对于每一个物品可能有多个这种可以预处理成一般的背包问题,就是把几个摊开,很简单就不解释了,当然也可以加一维.
还有就是完全背包问题他的状态转移方程是f[i,j]=max(f[i-1][j],f[i][j-data[i].v]);
他和01的区别只是要选的时候不是f[i-1][j-data[i].v]而是f[i][j-data[i].v],这样就能选到自己了,如果是初学可能不好理解,慢慢理会吧,其实这个很妙,我当初用了很多种方法,都是错的,看了一时也没明白,后来豁然开朗,然后对动规的理解都上了一个层次.
还有就是多为背包,这个只需要加一维,理解了前面的自然就能做出来了,根本不需要再看状态转移方程了(事实上理解后01就能够做出来了).
一句话:要多思考,反复思考
我很久没碰算法了,我没现成的代码这是我手打出来的,求分

❹ c语言的穷举法的背包问题

根据题目c1,c2是一组01组合的数组,也就是2个n位2进制数。
所以我的代码逻辑就是,c1,c2初值分别是00000....以及111111....,之后循环执行c1+1;c2-1(2进制加减运算),最大执行次数2的n次方-1(n位2进制数最大数)

代码实现功能,穷举所有可能方案,返回:第一个/最后一个找到的可行方案。

函数intqj(BAGc1,BAGc2,intn,int*bws,intflag);
当flag=1返回第一个可行方案,flag=0查找所有方案并返回最后一个可行方案
我测试时,flag传值0,需要自己改!!

由于迭代顺序,同样实验数据,返回的结构和你案例结构不一样,我在下图标注了。

#include<stdio.h>
#include<math.h>
#include<malloc.h>
#include<string.h>
typedefstructbag
{
intbweight;
char*books;
}BAG;
intqj(BAGc1,BAGc2,intn,int*bws,intflag);//穷举所有n位2进制组合,返回最后一个可行方案(可能有多个方案)。
//参数:c1背包1,c2背包2,n书本个数,bws所有书本重量,标识:flag=1找到第一个可行方案截止,flag=0查找所有方案
intcheckOverLoad(BAGc1,BAGc2,int*bws,intn);
voidadd2(char*nums);//2进制字符串+1运算
voidsub2(char*nums);//2进制字符串-1运算
intmain()
{
BAGc1,c2;
inti,n,*bws,sum=0;
printf("请输入两个背包的最大载重: ");
scanf("%d%d",&c1.bweight,&c2.bweight);
printf("请输入书本的数量: ");
scanf("%d",&n);
c1.books=(char*)malloc(sizeof(char)*(n+1));
c2.books=(char*)malloc(sizeof(char)*(n+1));
c1.books[0]=0;
c2.books[0]=0;
bws=(int*)malloc(sizeof(int)*n);
while(1)
{
sum=0;
printf("请输入每本书的重量: ");
for(i=0;i<n;i++)
{
scanf("%d",&bws[i]);
sum+=bws[i];
}
if(sum<=c1.bweight+c2.bweight)
break;
else
printf("书本重量和超过背包负重和!请重新输入 ");
}


qj(c1,c2,4,bws,0);
//------------------------------打印结果-----------------------------
printf(" 输出: ");
printf("book");
for(i=0;i<n;i++)
printf("%d",bws[i]);
printf(" ");
printf("c1%s ",c1.books);
printf("c2%s ",c2.books);
}
intqj(BAGc1,BAGc2,intn,int*bws,intflag)//穷举所有n位二进制数,
{
inti,max=(int)pow(2,n)-1;

char*nums1,*nums2;
nums1=(char*)malloc(sizeof(char)*(n+1));
nums2=(char*)malloc(sizeof(char)*(n+1));

printf("---------开始穷举所有可能的组合---------- ");
memset(c1.books,'0',n);
memset(c2.books,'1',n);
c1.books[n]=c2.books[n]=0;
printf("%s ",c1.books);
printf("%s ",c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memset(nums1,0,n+1);
memset(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return0;
}
printf(" ");
for(i=0;i<max;i++)
{
add2(c1.books);
sub2(c2.books);
printf("%s ",c1.books);
printf("%s ",c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memset(nums1,0,n+1);
memset(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return0;
}
printf(" ");
}
printf("-----------------穷举结束------------------ ");
memset(c1.books,0,n+1);
memset(c2.books,0,n+1);
strcpy(c1.books,nums1);
strcpy(c2.books,nums2);
free(nums1);
free(nums2);
return0;
}
voidadd2(char*nums)//2进制字符串加1
{
inti,n=strlen(nums),jin=0;
for(i=n-1;i>=0;i--)
{
if(nums[i]=='0'&&i==n-1)
{
nums[i]='1';
break;
}
elseif(nums[i]-'0'+jin==1&&i<n-1)
{
nums[i]='1';
break;
}
else
{
jin=1;
nums[i]='0';
}
}
}
voidsub2(char*nums)//2进制字符串减1
{
inti,n=strlen(nums),j=0;
for(i=n-1;i>=0;i--)
{
if(nums[i]=='1'&&i==n-1)
{
nums[i]='0';
break;
}
elseif(nums[i]-'0'-j==0&&i!=n-1)
{
nums[i]='0';
break;
}
else
{
nums[i]='1';
j=1;
}
}
}
intcheckOverLoad(BAGc1,BAGc2,int*bws,intn)//检查是否超载。超载返回1,否返回0
{
inti,sum1=0,sum2=0;
for(i=0;i<n;i++)
if(c1.books[i]=='1')
sum1=sum1+bws[i];
else
sum2=sum2+bws[i];
if(sum1>c1.bweight)
{
printf("背包1超载! ");
return1;
}
if(sum2>c2.bweight)
{
printf("背包2超载! ");
return1;
}
printf("方案可行! ");
return0;
}

❺ C语言实现背包问题,高手进来补填

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
long int m,n,w,p,i,j;
long int x[1001];
cin>>w>>p;
for(i=0;i<=1001;i++)
x[i]=0;
for(i=1;i<=n;i++)
{
cin>>a>>b;
if(m-a>0)
for(j=m-a;j>=0;j--)
if(x[j]+b>x[j+a]) x[j+a]=x[j]+b;
}
cout<<x[m]<<endl;
return 0;
}

❻ 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语言编程

原始题目: 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是
w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容
量,且价值总和最大。(取自网络)
问题简化: 1. 背包可容纳总重量为M
2. 有n个物品,每个重量为m[0]. m[1]. m[2] ......m[i] 对应每个物品的
价值为s[0]. S[1]. S[2]....s[i] (i<=n)
3. 放入第i个物品,比较m[i]和M的大小,不超过M则记录下当前价值s
4. 最终取得最大值s

实现方法:
定义三个浮点型一维数组float m[[n]和s[n]和y[n] 定义float M,float a,b定义int n,j, int i

请输入背包容量大小M:
please input the number of the things:
please input the value of the things:
把输入数据按顺序分别定义到数组中(若可以的话,把m[n]的数据由小到大排序,判断最小值m[0]和M的大小,若m[0]>M,输出error)
创建一个栈(这里的东西不太懂—-—)
将第一个数据压入栈底,定义i=0,把当前的m[i]赋值给a,s[i]赋值给b,把当前i存放进数组y[n],以后在每次比较过程中,都把较大b值所对应的物品数存放进y[n]中
判断a<M(这里,若在4已经做过,则可省略,第一个数据一定小于M)
判断a+m[++i]<=M,为真,把第i(注意,此时i已经自增了,这个i是数组中的下标)个数据压入栈,赋值a=a+m[++i],比较b和b+s[++i]的大小,赋值b=b+s[++i](理论上,物品价值总该是为正的吧,若是这样的话,不用比较大小了,直接赋新值,直到跳出第一轮循环为止;另外有一种设想,若价值全为正,可以转而把问题这样简化:即给定容量大小和全为正的价值物品,现在想办法让背包放入物品的数量最多 就行了);若为假,转10
如此进行一轮循环,直到出现10,此时b为一轮循环的最大值,return b,y[n]
当a+m[++i]>M,从栈中弹出m[i-2],a=a-m[i-2],,当i原本就小于等于2的时候,则清除栈中数据,转12,判断a+m[i]<=M,为真,比较b和b-s[i-2]+s[i],并把较大值赋给b,继续向下比较,这时候就不用压入栈中了,再定义一个j=1
判断a+m[i+j]<=M,为真,比较b和b-s[i-2]+s[i+j]大小,较大值赋给b,为假,从栈中弹出m[i-3],当i原本就小于等于3的时候,则清除栈中数据,转12,判断a+m[i]<=M,为真,比较b和b-s[i-3]+s[i](注意,这个b一直在被赋予最新值),如此进行第一轮循环,用for语句实现,因为下面还有嵌入
此时栈中没有数据,并且,已经把m[0]为栈底的循环计算完毕,现在开始计算m[1]为栈底的循环,在这一循环,忽略掉m[0],所有可能情况已经在8-11计算过

依此往下,直到栈底被压入的是m[n]为止,计算完毕,输出b,并且输出数组y[n]
碰巧帮同学,也是这个问题,希望能帮助你。

❽ 背包问题(C语言)

我一下别人的递归算法,假如你有时间限时的话,那我就用动态规划帮你重新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);
}

❾ C语言算法求助:背包问题

//如果每种商品只有一件,是0-1背包问题
读入的数据N代表物品个数
V代表背包容量。
//对于你的例子
,输入为
//5
16
//2
3
//3
2
//4
3
//5
7
//6
9
//输出为21
#include
<iostream>
using
namespace
std;
#define
MAXSIZE
1000
int
f[MAXSIZE
+
1],
c[MAXSIZE
+
1],
w[MAXSIZE
+
1];
int
main()
{
int
N,
V;
cin
>>
N
>>
V;
int
i
=
1;
for
(;
i
<=
N;
++i)
{
cin
>>
c[i]
>>
w[i];
}
for
(i
=
1;
i
<=
N;
++i)
{
for
(int
v
=
V;
v
>=
c[i];
--v)
//c[i]可优化为bound,
bound
=
max
{V
-
sum
c[i,...n],
c[i]}
{
f[v]
=
(f[v]
>
f[v
-
c[i]]
+
w[i]
?
f[v]
:
f[v
-
c[i]]
+
w[i]);
}
}
//当i=N时,可以跳出循环单独计算F[V]
cout
<<
f[V]
<<
'\n';
system("pause");
return
0;
}
//如果每种可以有多个,是完全背包问题,