1、01–背包问题
01–背包问题:就是有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?一个物品只有装与不装两种选择,不能只放一部分。
样例输入
5 10
6 3 5 4 6
2 2 6 5 4
样例输出
15
11001
1.从最后一个物品填表格
2. 从第一个物品填表格
从最后一个物品填表格
#include<bits/stdc++.h>
using namespace std;
int w[1005];
int v[1005];
int m[105][105];
int main()
{
int n,c;
while(~scanf("%d %d",&n,&c))
{
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int j=1;j<=n;j++)
scanf("%d",&w[j]);
int min1=min(w[n]-1,c);防止数组越界,物品的重量超过背包的容量了
for(int i=0;i<=min1;i++)//小于w[n]的填0
m[n][i]=0;
for(int j=w[n];j<=c;j++)//大于等于w[n]的填v[n]
m[n][j]=v[n];
for(int i=n-1;i>=1;i--)
{
int min2=min(w[i]-1,c);//防止数组越界,物品的重量超过背包的容量了
for(int j=0;j<=min2;j++)
m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
printf("%d\n",m[1][c]);
}
return 0;
}
2、构造最优解
如果选择从最后一个物品填表格(第一个物品),那么构造最优解的时候就从右上角(右下角)出发,比较i行和i+1行正下方的数字是否相同,不相同则选择了i行的物品,然后再j-w[i]列i行和i+1行数字是否相同;相同则往下一行同一列比较数字是否相同。
#include<bits/stdc++.h>
using namespace std;
int w[1005];
int v[1005];
int m[105][105];
int main()
{
int n,c;
while(~scanf("%d %d",&n,&c))
{
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int j=1;j<=n;j++)
scanf("%d",&w[j]);
int min1=min(w[n]-1,c);防止数组越界,物品的重量超过背包的容量了
for(int i=0;i<=min1;i++)//小于w[n]的填0
m[n][i]=0;
for(int j=w[n];j<=c;j++)//大于等于w[n]的填v[n]
m[n][j]=v[n];
for(int i=n-1;i>=1;i--)
{
int min2=min(w[i]-1,c);//防止数组越界,物品的重量超过背包的容量了
for(int j=0;j<=min2;j++)
m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
printf("%d\n",m[1][c]);
for(int i=1;i<n;i++)
{
if(m[i][c]==m[i+1][c])//不装
printf("0");
else
{
printf("1");//装
c=c-w[i];
}
}
if(m[n][c]>0)//最后一个物品的判断
printf("1");
else
printf("0");
printf("\n");
}
return 0;
}
3、动态规划法求解01-背包问题的局限性
背包的容量、物品的重量均只能是正整数。因为我们在使用动态规划求解01背包问题的时候,是将背包的容量已经物品的重量作为填表格的列来处理的,我们知道数组的行和列均只能是正整数。