完全背包：数组组合,买书

数字组合

原题链接：https://www.acwing.com/problem/content/280/

思路

可以看出是一个完全背包，下面来分析

完全背包dp

状态表示
集合：f[i][j]表示从前i个选，数字总和为j的方案的集合
属性：方案的数量num
状态转移
f[i][j]
[0,1,2,3,...,k]
第i个物品选0,1,...k个
	选0个:相当于不选f[i-1][j](从前i-1选，和为j)
	选k个:if(j-k*v[i] >= 0) f[i-1][j-k*v[i]]

回忆：完全背包优化

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
	f[i][j]=max(f[i,j-v]+w , f[i-1][j]) 

边界问题

直接使用完全背包优化成1维的结论f[j]+=f[j-w[i]]
(注意状态表示的定义，f[j-w[i]]表示的就是和为j-w[i]，时时刻刻记着去结合最初的状态表示定义)

这个题需要注意一下边界，f[0]的时候表示和为0的方案数，即f[0]=1

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int f[N];
int w[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n;i ++) cin >> w[i];
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= w[i]; j --)
            f[j] += f[j - w[i]];
    cout << f[m] ;
    return 0;
}

买书

原题链接：https://www.acwing.com/problem/content/1025/

思路

同上题，注意边界f[0]=1

代码

#include<iostream>

using namespace std;

const int N = 1010;
int v[5]={0,10,20,50,100};
int n;
int f[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= 4;i ++)
    {
        f[0] = 1;
        for(int j = v[i]; j <= n;j ++)
        {
            f[j] += f[j-v[i]];
        }
    }
    cout << f[n];
    return 0;
}