回溯法解01背包问题（C语⾔版）
问题描述：
给定N中物品和⼀个背包。物品i的重量是W i，其价值位V i，背包的容量为C。问应该如何选择装⼊背包的物品，使得转⼊背包的物品的总价值为最⼤？？
在选择物品的时候，对每种物品i只有两种选择，即装⼊背包或不装⼊背包。不能讲物品i装⼊多次，也不能只装⼊物品的⼀部分。因此，该问题被称为0-1背包问题。
问题分析：令V(i,j)表⽰在前i(1<=i<=n)个物品中能够装⼊容量为就j(1<=j<=C)的背包中的物品的最⼤价值，则可以得到如下的动态规划函数:
(1)  V(i,0)=V(0,j)=0
(2)  V(i,j)=V(i-1,j)  j<w i
V(i,j)=max{V(i-1,j) ,V(i-1,j-w i)+v i) } j>w i
(1)式表明：如果第i个物品的重量⼤于背包的容量，则装⼈前i个物品得到的最⼤价值和装⼊前i-1个物品
得到的最⼤价是相同的，即物品i不能装⼊背包；第(2)个式⼦表明：如果第i个物品的重量⼩于背包的容量，则会有⼀下两种情况：(a)如果把第i个物品装⼊背包，则背包物品的价值等于第i-1个物品装⼊容量位j-w i的背包中的价值加上第i个物品的价值v i; (b)如果第i个物品没有装⼊背包，则背包中物品价值就等于把前i-1个物品装⼊容量为j的背包中所取得的价值。显然，取⼆者中价值最⼤的作为把前i个物品装⼊容量为j的背包中的最优解。
01背包的状态转换⽅程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] }
以下是测试数据截图，背包容量:10
/*test.h*/
#include<stdio.h>
//-------------宏定义------------
#define OK 0
//-----------变量声明--------------
int x[100],bestx[100];
int cv = 0,cw = 0,mw = 0,mv = 0;
int c,n;
int weight[100];
int value[100];
//-------------函数声明------------
int Output();
int Input();
void Init();
bool place(int t);
void Track(int t);
/*test.cpp*/
#include"test.h"
void Init()
{
int i;
for(i = 0;i<100;i++)
{
x[i] = 0;
bestx[i] = 0;
weight[i] = 0;
value[i] = 0;
}
}
int Input()
{
int i;
printf("请输⼊背包的容量:");
scanf("%d",&c);
printf("请依次输⼊物品的重量:");
for(i=0;i<n;i++)
scanf("%d",(weight+i));
printf("请依次输⼊物品的价值:");
for(i=0;i<n;i++)
scanf("%d",(value+i));
return OK;
}
int Output()
{
printf("选择的物品是:");
for(int m = 0;m<n;m++)
printf("%d  ",bestx[m]);
明解c语言
printf("\nmax value is :%d\n",mv);
return OK;
}
bool place(int t)
{
if(cw+weight[t] > c)
return false;
return true;
}
//---------回溯法解01背包问题-----------------void Track(int t)
{
int m;
if(t>=n)
{
//output
if(cv>mv)
{
mv=cv;
for(m = 0;m<n;m++)
bestx[m] = x[m];
}
}
else
{
for(m = 0;m<=1;m++)
{
x[t] = m;
if(x[t] == 0)
{
Track(t+1);
x[t] = 0;
}
else if(place(t) && x[t]==1)
{
cv = cv + value[t];
cw = cw + weight[t];
Track(t+1);
x[t] = 0;
cv = cv - value[t];
cw = cw - weight[t];
}
}
}
}
void main()
{
Init();
printf("请输⼊物品的数量:"); scanf("%d",&n);
Input();
Track(0);
Output();
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。