背包问题---递归及动态规划

时间:2021-03-08 18:41:05

一、原题

假设有一组物品,各个物品的质量已知,现有一个背包,背包能够容纳的质量总和S已知,问能否从这N个物品中取出若干个恰好装入这个背包中。

二、递归算法

本质思想:设法尝试所有组合,当部分组合已经无法满足条件时,立即停止当前组合的尝试;若出现第一个满足条件的组合,立即停止尝试。使用递归回溯法实现。(感觉这东西不是我这种菜鸟能够说明白的,还得自己慢慢体会,最好的方法就是耐住性子跟踪调试)。

上“酸菜”

#include <stdio.h>
#include <stdlib.h>

#define N 7//物品种类
#define S 15//背包容量
int w[N+1]={0,1,4,3,4,5,2,7};//各种物品的质量

bool knap(int s,int n)//s代表背包剩余容量,n代表还未尝试装载的物品种类
{
if(s==0)//恰好装完
{
return true;
}
if(s<0 || (s>0 && n<1))//不能完成装载
{
return false;
}

if(knap(s-w[n],n-1))//当前物品能够装载,则递归
{
printf("%d",w[n]);
return true;
}
else
{
return knap(s,n-1);//当前物品不能装载,取下一物品进行递归
}
}

int main(void)
{
if(knap(S,N))
{
printf("OK!!!\n");
}
else
{
printf("NO!!!\n");
}

system("pause");
return 0;
}

背包问题---递归及动态规划
上面的代码仅仅输出了第一个满足条件的组合,那么怎样输出全部的有效组合呢?

#include <stdio.h>
#include <stdlib.h>

#define N 7
#define S 15
int w[N+1]={0,1,4,3,4,5,2,7};

//
int save[N+1]={0};//标记数组

int knap(int s,int n)
{
if(s==0)
{
return 1;
}
if(s<0 || (s>0 && n<1))
{
return 0;
}

if(knap(s-w[n],n-1))
{
//printf("%4d",w[n]);
//
save[n]=1;
return 1;
}
return knap(s,n-1);
}

void showSet(void)
{
for(int i=N;i>0;i--)
{
if(save[i]==1)
{
printf("%4d",w[i]);
}
}
}

int main(void)
{
bool flag;
for(int i=N;i>0;i--)//不断减少物品的种类,以便遍历所有组合
{
//
for(int m=0;m<N+1;m++)
{
save[m]=0;
}


if(knap(S,i))
{
showSet();
printf("\nOK!\n");
//
flag=true;//当物品种类为i时,存在有效组合
}
else
{
//printf("\nNO!\n");
flag=false;
}

//
while(flag)
{
int j=N;
int cnt=0;
int s_index=0;
while(j!=0 && cnt!=2)
{
if(save[j]==1)
{
cnt++;
}
if(cnt==1)
{
s_index=j;
}
j--;
}
if(cnt==2)
{
for(int k=0;k<s_index;k++)
{
save[k]=0;
}

if(knap(S-w[s_index],j))//从有效组合第二个物品的下一个物品开始寻找
{
showSet();
printf("\nOK!\n");
}
else
{
flag=false;
}

}
else
{
flag=false;
}
}

}

system("pause");
return 0;
}

背包问题---递归及动态规划

举例来讲,由于第一个有效的组合是7,2,5,1,所以下一次从2的下一个数开始搜索,背包的容量变成8=15-7.

三、动态规划方法

详见参考1,这里可以将物品的质量作为它的价值,那么如果最大价值dp[N][S]等于S,则说明背包能够恰好装满。

#include <iostream>
using namespace std;
#define N 7
#define S 15
#define max(a,b) a>b?a:b

int w[N+1]={0,1,4,3,4,5,2,7};//各种物品的质量

int main(void)
{
int i,j;
int dp[N+1][S+1];

memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++)
{
for(j=0;j<S+1;j++)
{
if(j>=w[i])
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);//转移方程,其中w[i]可以看做各物品的价值
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}

printf("%d\n",dp[N][S]);
if(dp[N][S]==S)
{
printf("OK!!!\n");
}
else
{
printf("NO!!!\n");
}

system("pause");
return 0;
}

背包问题---递归及动态规划

四、其它背包相关问题

根据以上分析,加以变通即可。