部分板子优化中…

你好哇，我是flypig114
代码里有变量数组的注释，so…不多废话，直接上正题！

01背包

无优化

#include<bits/stdc++.h>
using namespace std;
#define ll int//为了方便修改类型
const ll N=1000;//辅助定义数组
ll n,m;//n是背包容量   m是物品数量
ll v[N], w[N];//v是物品的重量   w是物品的价值
ll i,j,dp[N][N];//辅助计算
int main()
{
	//背包与DP的开始 
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>v[i]>>w[i];
    }
    //进行处理 
    for(i=1;i<=m;i++) 
        for(j=n;j>=0;j--)  
        {
            if(j>=v[i])
            {
                dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
            }  
            else
            {
                dp[i][j]=dp[i-1][j];
            }              
        }
    //结束首战告捷 
  cout<<dp[m][n];
    return 0;
}

一维数组优化：

#include<bits/stdc++.h>
using namespace std;
#define ll int//为了方便修改类型
const ll N=1e5;//辅助定义数组
ll n,m;//n是背包容量   m是物品数量
ll v[N], w[N];//v是物品的重量   w是物品的价值
ll i,j,dp[N];//辅助计算
int main()
{
	//难度上升需要新方法 
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>v[i]>>w[i];
    }
    //重中之重（好像就这里改了） 
    for(i=1;i<=m;i++) 
    {
        for(j=n;j>=0;j--) 
        {
            if(j>=v[i])
            {
                dp[j]=max(dp[j-v[i]]+w[i], dp[j]);  
            }
        }
    }   
    //可以输出了 
   cout<<dp[n];
    return 0;
}

更进一步的常数优化：

#include<bits/stdc++.h>
using namespace std;
#define ll int//为了方便修改类型
const ll N=1000;//辅助定义数组
ll n,m;//n是背包容量   m是物品数量
ll v[N], w[N];//v是物品的重量   w是物品的价值
ll i,j,dp[N],lower,sum;//辅助计算
int main()
{
	//还要优化 
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>v[i]>>w[i];
    }
    //重中之重（这话怎么这么熟悉） 
	    for(i=1;i<=n;i++)
	{
	     if(i!=1)
		 {
		 sum+=v[i-1];	
		 }
 	   lower=max(m-sum,v[i]);
 	   for(j=n;j>=lower;j--)
	    {
 	       //if(j>=v[i])
 	       dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
 	   }
	}
    //赶紧的输出 
   cout<<dp[n];
    return 0;
}

完全背包问题：

#include<bits/stdc++.h>
using namespace std;
#define ll int//为了方便修改类型
const ll N=1e5;//辅助定义数组
ll n,m;//n是背包容量   m是物品数量
ll v[N], w[N];//v是物品的重量   w是物品的价值
ll dp[N],i,j;//辅助计算
int main(){
	cin>>n>>m;
  //输入
		for(i=1;i<=n;i++)
	{
        cin>>v[i]>>w[i];
  }
  //完全背包启动！
    for(i=1;i<=n;i++)
	{
    	for(j=0;j<=m;j++)
    	{
			if(j>=v[i])
    	    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    	}
	}
  //简简单单的输出
   cout<<"max="<<dp[m]<<endl;
    return 0;
}

多重背包问题：

无优化

#include<bits/stdc++.h>
using namespace std;
#define ll int//为了方便修改类型
const ll N=100000;//辅助定义数组
ll m,n;//n是背包容量   m是物品数量
ll v[N],w[N],s[N];//v是物品的重量   w是物品的价值   s是物品的数量。
ll dp[N],i,j,k;//辅助计算
int main()
{
	//忘说了输入顺序按需求更改（不会有人真题都不看就套板子吧？） 
    cin>>m>>n;
    for(i=1;i<=m;i++)
	{
	cin>>w[i]>>v[i]>>s[i];	
	}
	//熟悉的流程 
    for(i=1;i<=m;i++)
	{
  		for(j=n;j>=v[i];j--)
		{
  			for(k=1;k*v[i]<=j&&k<=s[i];k++)
			{
    			dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
			}
		}
	}
    //结束了？ 
    cout<<dp[n]<<endl;
    return 0;
    //结束了。 
}

二进制优化