1##
O（1）dp算法
01背包问题
堆硬币
本质：递归)
经典例题1
维护最大 区间和
思路：考虑两种情况
1.极端情况：所有数都为负数 输出ans=0
2.不断递归 取最大值
优化递归：dp[i]维护的是前i个数中的最大和
随着数值的不断输入 不断更新 所以其时间复杂度 为 O（1）
#include"bits/stdc++.h"
using namespace std;
int N,a,dp,ans=0;
int main()
{
cin>>N;
for(int i=0;i
01背包问题
先考虑最暴力的枚举
f[i][j]表示只看前i个物品 体积为j的情况的总价值
则需要枚举j属于【0~v】
状态转移公式：
f[i][j]=max(f[i-1][j]+f[i-1][j-v[i]])
初始化 f[0][0]
dp二维数组
#include
using namespace std;
const int N=1010;
int main()
{
int v[N],w[N];
int f[N][N];
int n,m;
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=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(v[i]<=j)//特判一下不能选的物品
{
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
}
int res=0;
for(int i=0;i<=m;i++)res=max(res,f[n][i]);
cout<
一维数组 在二维条件上优化：
#include
using namespace std;
const int N=1010;
int main()
{
int v[N],w[N];
int f[N];
int n,m;
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=m;j>=v[i];j--hyyhhhhht)//
{
//if(v[i]<=j)//特判一下不能选的物品
f[j]=max(f[j],f[j-v[i]]+w[i]);//要使此层为i-1，需要从后往前遍历
}
}
cout<
总结：
优化成一维数组需要考虑极限条件
！！PS：为了确保最后的输出最大值是从f【0】状态转移来的，需要令
memset(f,0x3f,sizeof f)
f[0]=0;
堆硬币
int dp[N][N];//最简单的01背包问题
int h[N];
int main()
{
int n,k;
cin>>n>>k;
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;i++){
cin>>h[i];
dp[i][0]=0;
// dp[i][j]表示的是从前i个里面选高度为j的堆数量
}
sort(h+1,h+1+n);
for(int i=1;i<=n;i++){
for(int j=1;j<=3000;j++)//测试点的最大高为3000
dp[i][j] = dp[i-1][j];
if(j>=h[i]){
dp[i][j]=min(dp[i-1][j],dp[i-1][j-h[i]]+1);
}
}
//计算过程结束
//接下来判断结果 特例
if(dp[n][k]==0x3f3f3f3f){
cout<<"-1";
return 0;
}
cout<res;
for(int i=n;i>=1;i--)//h已经按照升序排序 则需要从n到1遍历
//此过程为 倒着找硬币堆 并拉入stl
{
if(k>=h[i]&&dp[i-1][k-h[i]]+1==dp[n][k]){
res.push_back(h[i]);
k-=h[i];//已知到答案 一步步倒推每个元素
}
}
sort(res.begin(),res.end());//多解则按字典序排列
for(int i=0;i
