太典了。

大家闭着眼睛都能敲出来。（？）

#include <iostream>
using namespace std;
int T,M;
int t[1005],v[1005],dp[1005];
int main(){
	cin>>T>>M;
	for(int i=1;i<=M;i++){
		cin>>t[i]>>v[i];
	}
	
	for(int i=1;i<=M;i++){
		for(int p=T;p>=1;p--){
			if(p>=t[i]){
				dp[p]=max(dp[p],dp[p-t[i]]+v[i]);
			}
		}
	}
	cout<<dp[T];
}

T2 最长上升子序列

题目：

逆向防御导弹？）

#include <iostream>
using namespace std;
const int N=1e6+5;
int n;
int num[5005];
int dp[5005];
int ans=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		for(int j=i-1;j>=1;j--){
			if(num[j]<num[i]&&dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
			}
		}
		if(dp[i]==0)
		dp[i]=1;
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

T3 最大序列和

题目：

更新的式子同样很好找到。

要注意的只是判断的条件而已。

#include <iostream>
using namespace std;
int n,ans=-999999;
int num[200005],dp[200005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		dp[i]=num[i];
		if(i!=1&&dp[i-1]>=0){
			dp[i]=dp[i]+dp[i-1];
		}
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

T4 LCS

太典了，啧啧啧。

也是大家闭着眼睛也能敲出来的东西（？）

#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int max_,a1,b1;
string ans;
int main(){
	string a,b;
	getline(cin,a);
	getline(cin,b);
	int len1=a.length();
	int len2=b.length();
	//矩阵边边要从0开始，下标0为dp中的1.
	for(int i=0;i<len1;i++){
		for(int l=0;l<len2;l++){
			if(a[i]==b[l]) dp[i+1][l+1]=dp[i][l]+1;
			else dp[i+1][l+1]=max(dp[i][l+1],dp[i+1][l]);
			if(dp[i+1][l+1]>max_){
				max_=dp[i+1][l+1];
				a1=i+1;
				b1=l+1;
			}
		}	
	}
	while(a1>0&&b1>0){
		if(a[a1-1]==b[b1-1]){
			ans=a[a1-1]+ans;
			a1-=1;
			b1-=1;
		}
		else{
			if(dp[a1-1][b1]>dp[a1][b1-1])
			a1-=1;
			else
			b1-=1;
		}
	}
	cout<<ans;
}

题目：

是经典的01背包问题，在博客另一处有介绍，推出 状态转移方程即可。

代码如下。

#include <iostream>
using namespace std;
long long int T,n;
long long int t[10005],w[10005];
long long int dp[10000005];
int main(){
	cin>>T>>n;
	for(int i=1;i<=n;i++) 
	cin>>t[i]>>w[i];
	for(int i=1;i<=n;i++){
		for(int l=1;l<=T;l++){
			if(l>=t[i])
			dp[l]=max(dp[l],dp[l-t[i]]+w[i]);
		}
	}
	cout<<dp[T];
	return 0;
}

T2 摆花

题目：

计数dp

用填表法的思想可以得出更新dp数组的式子。

#include <iostream>
using namespace std;
const long long int x=1000007;
long long int n,m,a[104],dp[105][105];
//dp[i][j]记录有i种花，要摆j盆时的摆法。
int main(){
	dp[0][0]=1;//一种花都没有的话是一种情况。
	cin>>n>>m;
	for(long long int i=1;i<=n;i++)
	cin>>a[i];
	for(long long int i=1;i<=n;i++){
		for(long long int l=0;l<=m;l++){
			for(long long int p=0;p<=min(l,a[i]);p++){
				dp[i][l]=(dp[i][l]+dp[i-1][l-p])%x;//每次都取模。
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

T3 樱花

题目：

看题可以知道有些美学值是可以拿很多甚至无限次的，所以这是一个多重背包问题，可以用二进制优化将复杂度由O（n^3）优化至O（n^2 logn）

可以把没有次数限制的美学值次数设成一个比较大的数。

代码如下。

#include <bits/stdc++.h>
using namespace std;
int N,V;
int v[100000005],w[100000006],dp[100000005];
long long int hs,ms,he,me;
int main(){
	scanf("%lld:%lld %lld:%lld %lld",&hs,&ms,&he,&me,&N);
	he-=hs;
	if(me-ms<0)
	me=me-ms+60,he--,me+=he*60;
	else me = me - ms + he * 60;
	V=me;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS）
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		if(c==0) c=9999999;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=z*k;
			w[count]=x*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=z*c;
			w[count]=x*c;
		}
	}
	for(int i=1;i<=count;++i){
		for(int k=V;k>=0;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

T4 金明的预算方案

题目：

这题存附件数据技巧是开二维数组cost[x][y],x为第x件物品，当y为0时为这件物品本身，y为1时为第x件物品的附件1，y为2时为第x件物品的附件2。

然后每次选择有五种情况，

①只买主件
②买主件+附件1
③买主件+附件2
④买主件+附件1+附件2
⑤不买主件。

除了1和5冲突外，其他四个都能判断后更新新的dp值，顺序任意，枚举这五种情况，填表即可。

代码如下。

#include <iostream>
#include <cstring>
using namespace std;
int m,n;
int dp[70][40000];
int cost[70][5],imp[70][5];
int main(){
	cin>>m>>n;
	int c,im,f;
	for(int i=1;i<=n;i++){
		cin>>c>>im>>f;
		if(!f){
			cost[i][0]=c;
			imp[i][0]=im;
		}
		else{
			if(!cost[f][1]){
				cost[f][1]=c;
				imp[f][1]=im;
			}
			else{
				cost[f][2]=c;
				imp[f][2]=im;
			}
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			if(l-cost[i][0]>=0){
				dp[i][l]=max(dp[i-1][l],dp[i-1][l-cost[i][0]]+cost[i][0]*imp[i][0]);
				if(l-cost[i][0]-cost[i][1]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]);
				}
				if(l-cost[i][0]-cost[i][2]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][2]*imp[i][2]);
				}
				if(l-cost[i][0]-cost[i][1]-cost[i][2]>=0){
					dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]+cost[i][2]*imp[i][2]);
				}
			}
			else
			dp[i][l]=dp[i-1][l];
		}
	}
	cout<<dp[n][m];
	return 0;
}

总结：

记忆化搜索>dp？）。
代码写的好丑呀。（不是什么大问题就是）

问题：有N件体积为v，价值为w的物品。和一个体积为V的背包，求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

可以先定义一个二维数组dp[i][j]表示在第i件物品，体积为j的时候的总价值。
可以推出状态转移方程：

dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-v[i]]+w[i]）

由此可知用双重循环遍历所有物品和体积，可以推出答案即dp[N][V]的值。
代码如下。

//01背包问题。
#include <iostream>
using namespace std;
int N,V;//N件物品，V为背包容量。
int v[1005],w[1005];//v为物品的体积，w为物品的价值。
int dp[1005][1005];//dp[i][j]为价值量 i为第i件物品，j为背包剩余的容量。
//！！dp[0][0-1005]为0（有可能会有测试点测0,0）
int main(){
	cin>>N>>V;
	//存储数据。
	for(int i=1;i<=N;i++){
		cin>>v[i]>>w[i];
	}
	//状态转移方程：
	for(int i=1;i<=N;i++){
		for(int k=1;k<=V;k++){
			if(k<v[i])//如果第i个物品放不下。
				dp[i][k]=dp[i-1][k];//这个物品不拿。
			else
				dp[i][k]=max(dp[i-1][k],dp[i-1][k-v[i]]+w[i]);//不拿或拿。
		}
	}
	cout<<dp[N][V];//输出答案。
}

但是可以发现运用二维数组记录答案即浪费空间也浪费时间，有10000件以上物品的时候很容易超时。
所以可以把dp二维数组压缩成一维数组优化，即滚动数组优化。

打表可以发现，在递推的过程中只是用到了和上一层的数据。

所以可以数组下标只记录背包的体积 dp[V]，并通过不断的覆盖避免了记录大量无用数据的问题。（？）

（坑点）但是要注意的是，用一维数组滚动要避免可能要用的数据过早被覆盖的问题，表中正向体积V是不断增大的，小背包能装的东西大背包也一定能装，反过来就不一定了，所以要逆向去更新覆盖数组中的数据。

代码如下。

//01背包问题。
#include <iostream>
using namespace std;
int N,V;//N件物品，V为背包容量。
int v[1005],w[1005];//v为物品的体积，w为物品的价值。
int dp[1005];//dp[j]为体积为J时能装的价值量。 j为背包剩余的容量。
//！！dp[0][0-1005]为0（有可能会有测试点测0,0）
int main(){
	cin>>N>>V;
	//存储数据。
	for(int i=1;i<=N;i++){
		cin>>v[i]>>w[i];
	}
	//状态转移方程：
	for(int i=1;i<=N;i++){
		for(int k=1;k<=V;k++){
			if(k<v[i])//如果第i个物品放不下。
				dp[i][k]=dp[i-1][k];//这个物品不拿。
			else
				dp[i][k]=max(dp[i-1][k],dp[i-1][k-v[i]]+w[i]);//不拿或拿。
		}
	}
	cout<<dp[N][V];//输出答案。
}

完全背包问题（每件物品都有无限件）

问题：有N种体积为v，价值为w的物品。和一个体积为V的背包，每种物品的数量是无限的，求解将怎样将物品分配入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

因为物品无限所以可以变成0/1/2/3…背包问题（？）

诶嘿，设k为取用一种物品的数量，观察原来的状态转移方程，发现可以在原来的基础上做一些小更改。
dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-v[i]]+w[i]）
↓↓↓ ↓↓↓
dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-k*v[i]]+k*w[i]）
再用滚动数组优化
dp[j]=max ( dp[j] , dp[j-k*v[i]]+k*w[i]）

代码如下：

#include <iostream>
using namespace std;
int w[1005],v[1005],dp[1005];
int main(){
	int N,V; cin>>N>>V;//N为物品数量，V为背包体积。
	for(int i=1;i<=N;i++)
	cin>>v[i]>>w[i];
	for(int i=1;i<=N;i++){
		for(int j = V;j>=0;k++){
			for(int k=0;k<=j/v[i];k++)
			dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);//不用判断能不能装得下了。
		}
	}
	cout<<dp[V];
	return 0;
}

但是因为用到了三重循环，所以这是非常土的方法。

可以再打个表看看。

可以发现新的数据是来自于上一行数据和新产生的数据。
在01背包的滚动数组里，新的数据是来自于上一行和上一行的旧数据得出的。
所以在完全背包可以无需给取用的物品计数，直到拿不下为止，从0开始，顺向去求解dp[V]的值。

代码如下。

#include <iostream>
using namespace std;
int w[1005],v[1005],dp[1005];
int main(){
	int N,V; cin>>N>>V;//N为物品数量，V为背包体积。
	for(int i=1;i<=N;i++)
	cin>>v[i]>>w[i];
	for(int i=1;i<=N;i++){
		for(int k = 1;k<=V;k++){//顺向，要用到新数据。
			if(k>=v[i])//可以从v[i]开始省掉一次判断（优化。
			dp[k] = max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

非常的奇妙。

多重背包问题（要变成01背包问题吗？）

直接拆成01背包问题是可以的，也可以多加一层循环。

for(int l=0;l<=s[i]&&l*v[i]<=k;l++)

还有感觉非常帅气，短小精悍的saber简化代码。

#include <bits/stdc++.h>
using namespace std;
int dp[1005],n,t,v,w,s;
main()
{
    cin>>n>>t;
    while(n--)
    {
    cin>>w>>v>>s;
    while(s--)
    for(int j=t;j>=w;j--)
    dp[j]=max(dp[j],dp[j-w]+v);
    }
    cout<<dp[t];
}

二维费用背包问题（有坑点）（待续）