动态规划—课堂笔记=＞背包问题（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];
}