0-1背包
背包
2023-09-14 09:08:53 时间
0-1背包
1.题目
2.过程
（1）假如我们放进背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，这里的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。而对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这里，我们要明白：要把这件物品放进背包，就得在背包里面预留这一部分空间。
（2）假如我们不放进背包，f[i][j] = f[i - 1][j]，这个很容易理解。
因此，我们的状态转移方程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])
当然，还有一种特殊的情况，就是背包放不下当前这一件物品，这种情况下f[i][j] = f[i - 1][j]。
代码：
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int w[105], val[105];
int dp[105][1005];
int main()
{
int C, m;
cin >> C >> m;
for(int i=1; i<=m; i++)
cin >> w[i] >> val[i];
for(int i=1; i<=m; i++) //物品
for(int j=C; j>=0; j--) //容量
{
if(j >= w[i])
dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);
else //只是为了好理解
dp[i][j] = dp[i-1][j];
}
cout << dp[m][C] << endl;
return 0;
}
代码：
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int f[100],v[100],w[100];
int main(){
int C,N;
cin>>C>>N;
for (int i = 1; i <= N; i++)
cin>>w[i]>>v[i];
for (int i = 1; i <= N; i++)
for (int j = C; j >= w[i] ; j--)
f[j]=max(f[j-w[i]]+v[i],f[j]);
cout<<f[C]<<endl;
}