动态规划—课堂笔记=＞背包问题（2）

//二维01背包：
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])
//一维01背包：
for(int i=1;i<=n;i++)//物品种类
 for(int j=m;j>=w[i];j--)//背包容量
  f[j]=max(f[j],f[j-w[i]]+c[i]);
：空间优化后的代码
#####################01背包要求全部装满########################
1)背包求最大价值时边界直接将数组初始化全部置0；
2)考虑“刚好装满条件”：
     一开始背包承重为0这种情况满足“装满条件”则f[0]=0;
     背包承重为j(j!=0)但不满足则f[j]=-0x3f3f3f3f//不可以赋值为0
     max 除了dp[0]=0  其他初始化为-0x3f3f3f3f
     min 除了dp[0]=0  其他初始化为0x3f3f3f3f
     不必恰好装满，全初始化为0

 

#include<bits/stdc++.h>
#define quickly() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5+10;
int t,m,n,ma,sum; 
int w[N],dp[N];
int main(){quickly();cin>>n>>t;for(int i=0;i<n;i++)cin>>w[i];memset(dp,0x8f,sizeof(dp));dp[0]=0;for(int i=0;i<n;i++){//物品种类for(int j=t-1;j>=w[i];j--){//容量倒序dp[j]=max(dp[j],dp[j-w[i]]+1);ma=max(ma,dp[j]);//记录最大价值（歌曲数量）}}sum=t-1;while(dp[sum]!=ma){sum--;}cout<<ma+1<<" "<<sum+678;
}

for(int k=1;k<=T;k++)//组数for(int j=v;j>=0;j--;)//背包容量for(int i=1;i<=n;i++)//同一组里面的物品if(a[i]==k&&j-w[i]>=0)f[j]=max(f[j],f[j-w[i]+c[i];
#########################################
#include<bits/stdc++.h>
#define quickly() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
struct node{int c,w;}tp;
int f[12][10005];
vector<node>vc[12];
int n,v,m,a,b,c;
int main(){quickly();while(cin>>n>>v>>m){for(int i=0;i<=m;i++){vc[i].clear();}for(int i=0;i<n;i++){cin>>a>>b>>c;tp.c=b,tp.w=c;vc[a].push_back(tp);}for(int i=1;i<=m;i++)for(int j=0;j<=v;j++)f[i][j]=-1;for(int i=0;i<=v;i++){f[0][i]=0;}for(int i=1;i<=m;i++){int c,w;int len=vc[i].size();for(int j=0;j<len;j++){c=vc[i][j].c,w=vc[i][j].w;for(int k=v;k>=c;k--){if(f[i][k-c]!=-1)f[i][k]=max(f[i][k],f[i][k-c]+w);if(f[i-1][k-c]!=-1)f[i][k]=max(f[i][k],f[i-1][k-c]+w);}}}if(f[m][v]==-1)cout<<"Impossible"<<endl;else cout<<f[m][v]<<endl;}
}

#include<bits/stdc++.h>
#define quickly() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,m;
int main(){cin>>n>>m;int weight[n+5];for(int i=0;i<n;i++)cin>>weight[i];int dp[n+1][m+1];for(int i=0;i<=n;i++)dp[i][0]=1;for(int j=1;j<=m;j++)dp[0][j]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j];if(j>=weight[i-1]){dp[i][j]+=dp[i-1][j-weight[i-1]];}}}cout<<dp[n][m];
}