01背包问题 普通背包
//这里填你的代码^^
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1001][1001];
int v[1001],w[1001];
int main()
{
int N,V;
cin>>N>>V;
for(int i=1;i<=N;i++)
{
cin>>v[i]>>w[i]; //体积 价值
}
for(int i=1;i<=N;i++) //属性在 j体积下,放i个物品的价值
{
for(int j=1;j<=V;j++)
{
if(j<v[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); //递推关系(判断) 不放(=前一个物品,j体积下价值)
// 与 放(体积减少,价值增大)
}
}
cout<<dp[N][V];
}
//一维数组
将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。
为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，
但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。
（1）状态f[j]定义：NN 件物品，背包容量j下的最优解。
（2）注意枚举背包容量j必须从m开始。
（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，
f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，
则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
（4）例如，一维状态第i轮对体积为 33 的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]
正确应该是f[i - 1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序
枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，
所以此时实际计算的f[4]仍然是f[i - 1][4]。
（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」
，逆序则不会有这样的问题。
状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。
#include<iostream>
using namespace std;
#include<algorithm>
int dp[1005];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w;
cin>>v>>w;
for(int j=m;j>=v;j--) 从后往前
{
dp[j]=max(dp[j],dp[j-v]+w);
}
}
cout<<dp[m];
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
完全背包问题
//这里填你的代码^^
#include<iostream>
#include<algorithm>
using namespace std;
int fa[1005],v[1005],w[1005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w;
cin>>v>>w;
for(int j=v;j<=m;j++)
{
fa[j]=max(fa[j],fa[j-v]+w);
//如果01背包不倒着来，就相当于本来只能用1次的物品可以多次使用了
}
}
cout<<fa[m];
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
多重背包问题
//这里填你的代码^^
#include<iostream>
using namespace std;
#include<algorithm>
int fa[1005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,k;
cin>>v>>w>>k;
for(int j=m;j>=v;j--){
for(int s=1;s<=k&&v*s<=j;s++)
{//多重背包 是背包01问题的升级版,
//普通背包,在不考虑重复取同一个物品下,即只取一次,转移方程为 fa[j]=max(fa[j],fa[j-v]+w)
// 若两次,转移方程为 fa[j]=max(fa[j],fa[j-v*2]+w*2)
//明显发现 只需要列举一个次数,一一判断,转移方程如下
fa[j]=max(fa[j],fa[j-v*s]+w*s);
}
}
}
cout<<fa[m];
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
多重背包问题,二进制枚举
//这里填你的代码^^
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
int fa[2005];
struct node{
int v1,w1;
};
int main(){
int n,m;
cin>>n>>m;
vector<node>q;
for(int i=1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
//如果直接暴力的话 是 O N^3 必LTE ,
//可使用二进制 来模拟 次数 进行优化 时间复杂度为 2000*1000*11
//如 3 : 11
// 7 : 111
// 6 : 101
for(int k=1;k<=s;k*=2){
s-=k;
q.push_back({k*v,k*w}); //fa[j]=max(fa[j],fa[j-v*s]+w*s) 用一个vector存一下(v*s,w*s)
}
if(s>0)
q.push_back({s*v,s*w});
}
for(auto node: q){
for(int j=m;j>=node.v1;j--)
{
fa[j]=max(fa[j],fa[j-node.v1]+node.w1);
}
}
cout<<fa[m];
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
分组背包问题
//这里填你的代码^^
#include<iostream>
#include<algorithm>
using namespace std;
int v[105][105],w[105][105],s[105];
int fa[105];
// 一.属性
//
//1. 集合：从前i组物品中选,且总体积不超过j的所有方案的集合.
//2. 属性：最大值
// 二、状态计算：
// 1. 思想-----集合的划分
// 2. 集合划分依据：根据从第i组物品中选哪个物品进行划分.
// f[j] = max(f[j],[j - v[i][k]] + w[i][k]);
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int k=1;k<=s[i];k++)
{
cin>>v[i][k]>>w[i][k];
}
}
for(int i=1;i<=n;i++){ //i几个物品 ,j是体积 k是 i 有几组
for(int j=m;j>=1;j--) //从上枚举来优化
{ for(int k=1;k<=s[i];k++)
{if(j>=v[i][k])
fa[j]=max(fa[j],fa[j-v[i][k]]+w[i][k]);}
}
}
cout<<fa[m];
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
