简单01背包
有一个箱子容量为v(正整数，0<=v<=2000),同时有n个物品（0<n<=30),每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间最小
输入描述：一个整数v,表示箱子容量；一个整数n,表示有n个物品；接下来n个整数，分别表示这n个物品的各自体积
输出描述：一个整数，表示箱子的剩余空间
样例输入：
24 6
8 3 12 7 9 7
样例输出：
0
分析：
第一步:确定状态，用dp[i][j]表示前i个物品在容量为j的背包里可以装下的最大体积
第二步：确定状态转移方程：枚举最后一次决策--第i个物品放还是不放；
放： dp[i][j] = dp[i-1][j-v[i]]+v[i];
不放：dp[i][j] = dp[i-1][j];
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int v;//输入体积
int n;//输入物品个数
while(cin>>v>>n)
{
int Item[30];//保存物品体积
for(int i=1;i<=n;i++)
cin>>Item[i];
int dp[31][2001]={0};//前i个物体放入容量为j的背包总所能占用的最大体积
for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
{
if(Item[i]>j){
dp[i][j] = dp[i-1][j]; //如果第i个物体容量比背包大，则不放
}
else{
dp[i][j] =max(dp[i-1][j],dp[i-1][j-Item[i]]+Item[i]); //状态转移方程
}
}
cout<<dp[n][v]<<endl;
}
}
价值背包
有N件物品和一个容量为V的背包。第i件物品的容量是c[i],价值是w[i],求解将哪些物体装入背包可使价值总和最大。
这里注意：要分情况恰装满或者小于等于背包容量（初始化不同）
第二种情况
#include<iostream>
#include<cstring>
using namespace std;
const int MaxN =105;
const int MaxM=105;
int main()
{
int N;//行李箱的最大容量
int M;//物体的个数
int c[MaxM];//容量
int v[MaxM];
int dp[MaxN][MaxM];
while(cin>>N>>M)
{
for(int i=1;i<=M;i++)
{
cin>>c[i];
}
for(int i=1;i<=M;i++)
{
cin>>v[i];
}
for(int i=0;i<=M;i++)
{
dp[i][0]=0;
}
for(int j=0;j<=N;j++)
{
dp[0][j] =0;
}
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
{
if(c[i]>j) dp[i][j]=dp[i-1][j];
else{
dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);
}
}
cout<<dp[M][N];
}
}
完全背包
将状态方程改下即可
#include<iostream>
#include<cstring>
using namespace std;
const int MaxN =105;
const int MaxM=105;
int main()
{
int N;//行李箱的最大容量
int M;//物体的个数
int c[MaxM];//容量
int v[MaxM];
int dp[MaxN][MaxM];
while(cin>>N>>M)
{
for(int i=1;i<=M;i++)
{
cin>>c[i];
}
for(int i=1;i<=M;i++)
{
cin>>v[i];
}
for(int i=0;i<=M;i++)
{
dp[i][0]=0;
}
for(int j=0;j<=N;j++)
{
dp[0][j] =0;
}
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
{
if(c[i]>j) dp[i][j]=dp[i-1][j];
else{
dp[i][j] = max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
}
}
cout<<dp[M][N];
}
}
问题待解决
恰好装满的情况未能弄清楚
