题目描述

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M ，而价值的和为最大。

输入

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；第2..N+1 行：每行二个整数Wi,Ui，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值，格式如样例。

样例输入

10 4  2  1  3  3 4  5 7  9

样例输出

max=12

解析

\(dp(i,j)\)表示前\(i\)个物品装入\(j\)重量背包中能够得到的最大总价值。

状态方程1：

\(dp(i,j)=max\{dp(i-1,j-k\times w[i])+k\times v[i]\mid 0\leq k\}\)

\(dp(0,j)=0\quad dp(i,0)=0\)

程序片段：

const int MaxN=100,MaxW=10000;int dp[MaxN+1][Maxw+1];int n,w[MaxN+1],v[MaxN+1],W;/*输入*/cin>>W>>n;for(int i=1;i<=n;i++)    cin>>w[i]>>v[i];memset(dp,0,sizeof(dp));/*动态规划计算*/for(int i=1;i<=n;i++)    for(int j=1;j<=W;j++)        for(int k=0;k*w[i]<=k;k++)            dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]}+k*v[i]);cout<<"max="<
    
     <
    

空间复杂度：O(n*W);

时间复杂度：O(n*W*W);

状态方程2：

\[dp(i,j)=max\{dp(i-1,j-k\times w[i])+k\times v[i]\mid 0\leq k\}\]

即

\[ \begin{aligned} dp(i,j)=max\{&dp(i-1,j),\\ &\boxed{dp(i-1,j-w[i])}+v[i],\\ &\boxed{dp(i-1,j-2\cdot w[i])+v[i]}+v[i], \dots \} \end{aligned} \]

对比

\[ \begin{aligned} dp(i-1,j-w[i])=max\{&\boxed{dp(i-1,j-w[i])},\\ &\boxed{dp(i-1,j-2\cdot w[i])+v[i]},\\ &dp(i-1,j-3\cdot w[i])+2\cdot v[i], \dots\} \end{aligned} \]

得到

\[dp(i,j)=max\{dp(i-1,j),dp(i-1,j-w[i])+v[i]\}\]

程序片段（改进时间）：

/*动态规划计算*/for(int i=1;i<=n;i++)    for(int j=1;j

空间复杂度：O(n*W)

时间复杂度：O(n*W)

程序片段（压成一维）：

int dp[MaxN+1];/*动态规划计算*/for(int i=1;i<=n;i++)    for(int j=1;j
    
     W[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    

空间复杂度：O(W)

时间复杂度：O(n*W)

类似问题：牛奶容器

题目描述

农民保罗有如下型号的牛奶容器： 10加伦，2加伦，1 加伦，1/4加伦，1/8加伦， 1/16加伦。

请您帮他编写一个程序，能计算保罗用这些容器取X加伦牛奶共有多少不同方法。在所有的数据中，X都是整数且(1<=X<=100)。

输入

输入数据中有多组测试数据，每组测试数组仅有一行，包含一个整数x。最后一行以0表示结束。

输出

对于每组数据，输出一行，为保罗用这些容器取x加伦牛奶共有的不同方法数。

样例输入

5100

样例输出

130812477