动态规划DP

完全背包问题的模型如下：
给定N种物品，其中第i种物品的体积为Vi，价值为Wi，并且有无数个。有一个容积为M的背包，要求被选择的若干个物品放入背包中，使得总体积不超过M的情况下，物品的价值总和最大。
传统的二维线性DP的做法，设F[i, j]表示从前i中商品中选出体积总和为j的物品放入背包，物品的最大价值和。

	F[0, 0] = 0;
	F[i, j] = max(F[i - 1, j], F[i, j - Vi] + Wi]);
	F[i - 1, j]//尚未选第i中商品
	F[i, j - Vi] + Wi]//表示从i种商品中选一个

与0/1背包一样，我们也可以省略F数组的第一维。

	unsigned int f[MAX_M + 1];
	memset(f, 0, sizeof(f));
	f[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = v[i]; j <= m; j++)
		{
			f[j] = max(f[j - 1], f[j - v[i]] + w[i]);
		}
	}
	f[m]//最大价值

自然数拆分Lunatic版 CH5202
描述
给定一个自然数N，要求把N拆分成若干个正整数相加的形式，参与加法运算的数可以重复。求拆分的方案数 mod 2147483648的结果。1≤N≤4000。

输入格式
一个整数n。

输出格式
输出一个数，即所有方案数
因为这个数可能非常大，所以你只要输出这个数 mod 2147483648 的余数即可。

样例输入
7
样例输出
14
样例解释
输入7，则7拆分的结果是
7=1+6
7=1+1+5
7=1+1+1+4
7=1+1+1+1+3
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
7=1+1+1+2+2
7=1+1+2+3
7=1+2+4
7=1+2+2+2
7=1+3+3
7=2+5
7=2+2+3
7=3+4

一共有14种情况，所以输出14 mod 2147483648，即14

#include <iostream>
#include <string.h>
using namespace std;
const int MAX_M = 4000;
int main(void)
{
	unsigned int f[MAX_M + 1];
	memset(f, 0, sizeof(f));
	int n;
	cin >> n;
	f[0] = 1;//包含取n-n，在答案时-1
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
		{	//求方案数把背包模板max函数改为求和
			f[j] = (f[j] + f[j - i]) % 2147483648u;
		}
	}
	cout << (f[n] > 0 ? f[n] - 1: 2147483647) << endl; 
	return 0;
}

----------------------------------------------------------------
第二种解法


#include <iostream>
using namespace std;
const int MAX = 4e3 + 1; 
int a[MAX][MAX];
int f(int n)
{	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (j == 1)
			{
				a[i][j] = 1;
			}
			else if (j == i)
			{
				a[i][j] = a[i][j - 1] + 1;
			}
			else if (i < j)
			{
				a[i][j] = a[i][i];
			}
			else
			{
				a[i][j] = a[i][j - 1] + a[i - j][j];
			}
			a[i][j] %= 2147483648u;
		} 
	}
	if (a[n][n] == 0)
	{
		return 0;
	}
	return a[n][n] - 1; 
}
int main(void)
{
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}

将一个正整数n表示成一系列的正整数的和

#include <iostream>
using namespace std; 
int f(int n, int m)
{	//f(n, m) 表示正整数n的所有不同划分中，最大加数不大于m的划分个数 
	if (m == 1)
	{	//加数不大于1的划分只有一种 
		return 1;
	}
	else if (n < m)
	{	//不存在加数大于n的存在 
		return f(n, n);
	}
	else if (n == m)
	{	//n的最大加数为n的划分数加上n的最大加数不大于n的划分数 
		return f(n, m - 1) + 1;
	}
	else
	{	//最大加数不大于m-1的划分数加数n的最大加数为m的划分数 
		return f(n, m - 1) + f(n - m, m); 
	}
}
int main(void)
{
	int n;
	cin >> n;
	cout << f(n, n);
	return 0;
}