一、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了。
【写的伪代码，能看懂哈。。。不懂再问好了】陆亮
根据题目c1，c2是一组01组合的数组，也就是2个n位2进制数。所以我的代码逻辑就是，c1，c2初值分别是 00000....以及111111....，之后循环执行c1+1；c2-1（2进制加减运算），最大执行次数 2的n次方-1（n位2进制数最大数）
代码实现功能，穷举所有可能方案，返回:第一个 /最后一个找到的可行方案。
函数int qj(BAG c1,BAG c2,int n,int 早神*bws,int flag)
当flag=1 返回第一个可行方案，flag=0 查找所有方案并返回最后一个可行方案
我测试时，flag传值0，需要自己改！！
由于迭代顺序，同样实验数据，返回的结构和你案例结构不一样，我在下图标注了。 #include<stdio.h>
#include<math.h>
#include<malloc.h>
#include<string.h>
typedef struct bag
{
int bweight
char *books
}BAG
int qj(BAG c1,BAG c2,int n,int *bws,int flag)//穷举所有n位2进制组合，返回最后一个可行方案（可能有多个方案）。
//参数：c1背包1，c2背包2，n书本个数，bws所有书本重量，标识：flag=1 找到第一个可行方案截止，flag=0查找所有方案
int checkOverLoad(BAG c1,BAG c2,int *bws,int n)
void add2(char *nums)//2进制字符串+1运算
void sub2(char *nums)//2进制字符串-1运算
int main()
{
BAG c1,c2
int i,n,*bws,sum=0
printf("请输入两个背包的最大载重：\n")
scanf("%d%d",&c1.bweight,&c2.bweight)
printf("请输入书本的数量：\n")
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("请输入每本书的重量：\n")
for(i=0i<ni++)
{
scanf("%d",&bws[i])
sum+=bws[i]
}
if(sum<=c1.bweight+c2.bweight)
break
else
printf("书本重量和超过背包负重和！请重新输入\n\n")
}
qj(c1,c2,4,bws,0)
//------------------------------打印结果-----------------------------
printf("\n输出：\n")
printf("book ")
for(i=0i<ni++)
printf("%d ",bws[i])
printf("\n")
printf("c1 %s\n",c1.books)
printf("c2 %s\n",c2.books)
}
int qj(BAG c1,BAG c2,int n,int *bws,int flag)// 穷举 所有n位二进制数,
{
int i,max=(int)pow(2,n)-1
char *nums1,*nums2
nums1=(char *)malloc(sizeof(char)*(n+1))
nums2=(char *)malloc(sizeof(char)*(n+1))
printf("---------开始衡轿穷举所有可能的组合----------\n")
memset(c1.books,'0',n)
memset(c2.books,'1',n)
c1.books[n]=c2.books[n]=0
printf("%s\n",c1.books)
printf("%s\n",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)
return 0
}
printf("\n")
for(i=0i<maxi++)
{
add2(c1.books)
sub2(c2.books)
printf("%s\n",c1.books)
printf("%s\n",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)
return 0
}
printf("\n")
}
printf("-----------------穷举结束------------------\n")
memset(c1.books,0,n+1)
memset(c2.books,0,n+1)
strcpy(c1.books,nums1)
strcpy(c2.books,nums2)
free(nums1)
free(nums2)
return 0
}
void add2(char *nums)//2进制字符串加1
{
int i,n=strlen(nums),jin=0
for(i=n-1i>=0i--)
{
if(nums[i]=='0' && i==n-1)
{
nums[i]='1'
break
}
else if(nums[i]-'0'+jin==1 && i<n-1)
{
nums[i]='1'
break
}
else
{
jin=1
nums[i]='0'
}
}
}
void sub2(char *nums)//2进制字符串减1
{
int i,n=strlen(nums),j=0
for(i=n-1i>=0i--)
{
if(nums[i]=='1' && i==n-1)
{
nums[i]='0'
break
}
else if(nums[i]-'0'-j==0 && i!=n-1)
{
nums[i]='0'
break
}
else
{
nums[i]='1'
j=1
}
}
}
int checkOverLoad(BAG c1,BAG c2,int *bws,int n)//检查是否超载。超载返回1，否返回0
{
int i,sum1=0,sum2=0
for(i=0i<ni++)
if(c1.books[i]=='1')
sum1=sum1+bws[i]
else
sum2=sum2+bws[i]
if(sum1>c1.bweight)
{
printf("背包1超载！\n")
return 1
}
if(sum2>c2.bweight)
{
printf("背包2超载！\n")
return 1
}
printf("方案可行！\n")
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）