【动态规划】最长非降子序列 01背包 插入加号

给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数 构成非升子序列（即后面的项不大于前面的项），打印出最长的非升子序列。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[100]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
	int b[100]={0,48,16,45,47,52,46,36,28,46,69,14,42};
	a[1]=1;
	int lmax=0;
	for(int i=2;i<=12;i++)
	{
		int max=0;
		for(int j=i-1;j>=1;j--)
		{
			if(b[i]>b[j])
			{
				if(a[j]>max)max=a[j];
			}
		}
		a[i]=max+1;
		if(a[i]>lmax)lmax=a[i];	
	}
	cout<<"最长非降子序列的长度为"<<lmax<<endl;
	for(int i=12;i>=1;i--)
	{
		if(a[i]==lmax)
		{
			cout<<b[i]<<",";
			lmax--;
		}
	}
	return 0;
}

已知n种物品和一个可以容纳重量c的背包，物品i的重量为wi，产生的效益为pi。在装包时物品i可以装入，也可以不装入，但不可拆开装。如何选择这n个物品，使总收益最大？

#include<bits/stdc++.h>
using namespace std;
int MAX(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int n=6;//n种物品
	int c=60;//可容纳重量为60的物品
	int w[7]={0,15,17,20,12,9,14};//每件物品的重量
	int p[7]={0,32,37,46,26,21,30};//每件物品的价值 
	int a[100][100];//第一【】装了多少物品，第二个【】剩余多少容量，值产生的价值 
	for(int i=1;i<=n;i++)//n为6 
	{
		for(int j=1;j<=c;j++)//c为60 
		{
			if(j>=w[i])//当前容量大于等于当前物品的容量(可以拿) 
			{
				//可以拿的时候判断到底拿不拿 
				a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+p[i]);
			}
			else//当前容量小于当前物品的容量(不能拿) 
			{
				a[i][j]=a[i-1][j]; 
			} 
		}
	}
	cout<<"背包能装的最大价值为："<<a[n][c];
	return 0;
}

在一个n位整数a中插入r个加号，将它分成r+1个整数，找出一种加号的插入方法，使得这r+1个整数的和最小

#include<bits/stdc++.h>
using namespace std;
int sub(int number[],int start,int end); 
int main()
{
	char character[100];
	int number[100];
	int addnumber;
	int f[100][100];
	cout<<"请输入整数：";
	cin>>character; 
	cout<<"请输入+号的个数：";
	cin>>addnumber;
	int length=strlen(character);
	
	//将字符型转化为数字型 
	for(int i=0;i<length;i++)
	{
		number[i]=character[i]-48;
	}
	
	//赋初值 
	for(int i=1;i<=length;i++)
	{
		f[i][0]=sub(number,0,i); 
	}
	
	
	for(int i=1;i<=addnumber;i++) 
	{
		for(int j=i+1;j<=length;j++) 
		{
			int min=99999999; 
			for(int k=i;k<j;k++)
            {  
                int value=f[k][i-1]+sub(number,k,j); 
                if(value<min)  
                {  
                    min=value;  
                }  
            } 
			f[j][i]=min; 	
		} 
	}
	cout<<"最小值为："<<f[length][addnumber]; 
	return 0;
}
int sub(int number[],int start,int end)
{
	int count=0;
	for(int i=start;i<end;i++)
	{
		count=count*10+number[i];
	}
	return count;
}