01背包问题
题目:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
思路:
设物品件数:n,背包容量:m,第i件物品体积:vi,价值:wi
可从输入样例分析思路
输入样例:
4 5
1 2
2 4
3 4
4 5
可以列出个表来直观分析
相关分析
j为背包体积,i为物品件数,v[ i ]是当件数为第i时的物体体积,w[ i ]是当物体为第i件时物体价值
设dp [ i ][ j ]就是i件物品在背包容积为j时能装的最大价值
然后根据题目样例可以列出下表:
j=0 j=1 j=2 j=3 j=4 j=5
i=0 v[i],w[i] 0 0 0 0 0 0
i=1 1,2 0 2 2 2 2 2
i=2 2,4 0 2 4 6 6 6
i=3 3,4 0 2 4 6 6 8
i=4 4,5 0 2 4 6 6 8
该题可以分成两步分析,
1,当 v[ i ] > j 时,d[ i ][ j ]=d[ i - 1 ][ j ];
【这时,第 i 件物品的体积大于背包体积,不够装】
2,当v[ i ] < = j时,d[ i ][ j ]=max( d[i - 1][ j ],d[i - 1][j - v[ i ]]+w[ i ] )
_【这时,虽然够装第 i 件物品,但也有可能装这件物品,也有可能不装,假如装了第 i 件物品,反而还没有装之前背包含有的价值高,那就不装了。
所以现在就比较装第 i 件物品时背包的价值(d[i -1][j - v[ i ]]+w[ i ]),与不装第 i 件物品时背包的价值(d[i - 1][ j ])
取出它们二者的最大值,即为此时d[ i ][ j ]的最大值】
_
这就是用二维数组时的解法
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(v[i]>j)dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
}
cout<<dp[n][m]<<endl;
return 0;
}
如果想测试一下结果是否正确,可以加行这样的代码,来输出d[i][j]的表格
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
加后的代码如下
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(v[i]>j)dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
cout<<dp[n][m]<<endl;
return 0;
}
写下笔记,便于复习,如有错误或不恰当之处,望大佬指正QWQ