背包问题笔记（参考用）（板子？）

曾经终败给现在 2022-12-22 11:15 48阅读 0赞

/*0-1背包:只许选择一次 问题：有N个物品和一个容量为S的背包，第i件物品的重量是w[i]，价值是v[i]。在每种物品只许放一次，不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。 f[i][j]=f[i-1][j-w[i]]+v[i]和f[i-1][j]的较大项*/
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct thing{ 
    	int v,p;
    }want[30]; 
    long long c[10010],d[10010];
    int main()
    { 
    	int n,m;
    	cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{ 
    		cin>>want[i].v>>want[i].p;
    	}
    	for(int i=1;i<=m;i++)
    	{ 
    		for(int j=n;j>=want[i].v;j--)
    		{ 
    			c[j]=max(c[j],c[j-want[i].v]+want[i].v*want[i].p);
    		}
    	}
    	cout<<c[n]<<endl;
    	return 0;
    }
    /*完全背包：物品数量选择无限制 问题： 有N个物品和一个容量为S的背包，第i件物品的重量是w[i]，价值是v[i]。在每种物品有无限个，不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。*/
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct thing{ 
    	int v,p;
    }want[30];
    long long c[10010];
    int main()
    { 
    	int n,m;
    	cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{ 
    		cin>>want[i].v>>want[i].p;
    	}
    	for(int i=1;i<=m;i++)
    	{ 
    		for(int j=want[i].v;j<=n;j++){ 
    			c[j]=max(c[j],c[j-want[i].v]+want[i].p);
    		}
    	} 
    	cout<<c[n]<<endl;
    	return 0;
    }
    /*多重背包：物品数量有上限 有N个物品和一个容量为S的背包，第i件物品的重量是w[i]，价值是v[i]，上限是c[i]。在不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。*/
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct thing {  
      int v,p,s;
    } want[30];
    long long c[10010];
    int main() 
    {  
      	int n,m;       
      	cin>>n>>m;      
      	for(int i=1; i<=m; i++) 
      	{ 
      		cin>>want[i].v>>want[i].p>>want[i].s;        
      	}        
      	for(int i=1; i<=n; i++) 
    	{  
         	for(int j=m;j>=want[i].v; j--) 
    		{ 
             	for(int k=0;k<=want[i].s; k++)
    			 { 
                  	if(j >=k*want[i].v)
                  	{ 
                  		c[j]=max(c[j],c[j-k*want[i].v]+k*want[i].p); 
    				}
            	}          
         	}       
      	}          
      	cout << c[m] << endl;      
      	return 0;
    }
    /*混合背包 有N个物品和一个容量为S的背包，第i件物品的重量是w[i]，价值是v[i]，上限是c[i]（若为0则可取无限个）。在不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。*/
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct thing{ 
    	int v,p,s;
    }want[30];
    long long c[10010];
    int main()
    { 
    	int n,m;
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){ 
    		cin>>want[i].v>>want[i].p>>want[i].s;
    	}
    	for(int i=1;i<=m;i++){ 
    		if(want[i].s==0){ //完全背包
    			for(int j=want[i].v;j<=m;j++)
    			{ 
    				f[j]=max(f[j],f[j-w[i]+v[i]]);
    			} 
    		}
    		else
    		{ 
    			for(int j=m;j>=want[i].v;j--){ //0-1和多重背包
    				for(int k=0;k<=want[i].s;k++){ 
    					if(j>=k*want[i].v)
    					{ 
    						c[j]=max(c[j],c[j-k*want[i].v]+k*want[i].p);
    					}
    				} 
    			}
    		}
    	}
    	cout<<c[m]<<endl;
    	return 0;
    }
    //0-1背包最优解 
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,s,f[100],w,v;
    int main()
    { 
    	cin>>n>>s;
    	for(int i=1;i<=n;i++)
    	{ 
    		cin>>w>>v;
    		for(int j=s;j>=w[i];j--)
    		{ 
    			f[j]=max(f[j],f[j-w]+v);
    		}
    	}
    	cout<<f[s]<<endl;
    	return 0;
    }