01背包问题是比较简单的动态规划问题，题目大意为：
有N件物品和一个容量为V的背包。每种物品均只有一件，第i件物品的重量（费用）是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
核心思想，就是这句代码：
sum[i][j] = Max(sum[i - 1][j], sum[i - 1][j - c[i]] + v[i])
其中sum[i][j]表示的是把前i件物品，放在承重为 j 的背包中，可以取得的最大价值，那么我们要做的判断就是，为了让重量（价值）最大化，是否需要把第i个物品放入背包中？
这里举个例子，现有一个容量为5的背包，有三个物品：
物品a，价值为1，重量为2
物品b，价值为2，重量为1
物品c，价值为4，重量为4
可以列出表格
1111.png
接下来要做的，就是用
sum[i][j] = Max(sum[i - 1][j], sum[i - 1][j - c[i]] + v[i])
将其填上，别忘了先把sum初始化。
定义数组c[i]为物品i的重量,v[i]为物品i的价值。
ok下面我们开始填表：
a行
放入条件j > c[1] = 2，其中j是背包的容积
sum[1][1] = 0;(j < c[1]放不进)
sum[1][2] = max(sum[0][2],sum[0][0] + 1) = 1;
sum[1][3] = max(sum[0][3],sum[0][1] + 1) = 1;
sum[1][4] = max(sum[0][4],sum[0][2] + 1) = 1;
sum[1][5] = max(sum[0][5],sum[0][3] + 1) = 1;
b行
放入条件j > c[2] = 1
sum[2][1] = max(sum[1][1],sum[1][0] + 2) = 2;
sum[2][2] = max(sum[1][2],sum[1][1] + 2) = 2;
sum[2][3] = max(sum[1][3],sum[1][2] + 2) = 3;
sum[2][4] = max(sum[1][4],sum[1][3] + 2) = 3;
sum[2][5] = max(sum[1][5],sum[1][4] + 2) = 3;
c行
放入条件j > c[3] = 4
sum[3][4] = max(sum[2][4],sum[2][0] + 4) = 4;
sum[3][5] = max(sum[2][5],sum[2][1] + 4) = 6;
所以，可得到表
12.png
可以看出我们需要的最大值Max = sum[3][5]，即sum[n][k],k为背包总重量，n为总共有几个物品。
最后再次强调
sum[i][j] = Max(sum[i - 1][j], sum[i - 1][j - c[i]] + v[i])
把前i个物品放入容量为j的背包可得的最大价值。
当然在是思考这个问题的时候，我们还应该考虑，怎样是最优情况，比如以下数据：
背包重量为10，有3个物品，其重量和价值分别为
物品1：价值为4，重量为5；物品2：价值为6，重量为5；物品3：价值为10，重量为10。
那我们应该如何选择？
代码如下
#include <stdio.h>
int sum[1001][1001],x[1001][1001];
//sum[i][j]放入第i个物品，j空间的背包最大重量
int Max(int a,int b);//判断大小
void init(int b);//初始化背包
void scok(int n,int t,int* c,int* v);//核心判断
int Max(int a,int b)
{
if(a > b)
return a;
else
return b;
}
void init(int b)
{
for(int j = 0;j <= b;j++)
{
x[0][j] = 0;
sum[0][j] = 0;
}
}
void scok(int n,int k,int* c,int* v)
{
int i,j;
init(k);
for(i = 1;i <= n;i++) //背包问题的核心，判断是否要放入第i个物品
for(j = 1;j <= k;j++)
{
if(j >= c[i])
{
sum[i][j] = Max(sum[i - 1][j], sum[i - 1][j - c[i]] + v[i]);
if(sum[i][j] > sum[i - 1][j - c[i]] + v[i])
x[i][j] = x[i - 1][j];
else if(sum[i][j] == sum[i - 1][j - c[i]] +v[i])//如果放入，标记数组x加1
{
x[i][j] = x[i - 1][j - c[i]] + 1;
}
}
else
{
sum[i][j] = sum[i - 1][j];
x[i][j] = x[i - 1][j];
}
//防止出现选择非最优化情况，即在同等重量的情况下，选择的物品过多
if(sum[i][j] == sum[i - 1][j] && x[i][j] > x[i - 1][j])
x[i][j] = x[i - 1][j];
}
printf("%d %d\n",sum[n][k],x[n][k]);
}
int main()
{
int k,c[1001],v[1001],n,t;
//k,n,t分别为背包总重量，有几个物品，有几组背包数据
scanf("%d",&t);
while (t--)
{
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;i++)
scanf("%d %d",&v[i],&c[i]);//c[i]为i物品的重量，v[i]为i物品的价值
scok(n, k, c, v);
}
return 0;
}
第一次开始写博客，有什么不周到的，请大家及时指出，谢谢。
网友评论