学习了01背包，现在进一步探讨递推关系，完全背包问题
题目：有n种重量和价值分别为wi,vi的物品，从这些物品种选出总重量不超过W的物品，求出挑选物品价值总和的最大值。在这里，每种物品可以挑选任意多件
限制条件：1<=n<=100,1<=wi,vi<=100,1<=W<=10000
输入：n=3 (w,v)=((3,4),(4,5),(2,3)) W=7
输出：10
和01背包相比，这次同一种类的物品可以选择任意多件。 我们试着写出递推关系
令dp[i+1[j]:=从第i个物品到第n-1个物品中挑选总总量不超过j时总价值的最大值。 那么递推关系为：
dp[i][j]=max(dp[i][j],dp[i+1][j-k*w[i]]+k*v[i])
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<set>
typedef long long ll;
using namespace std;
int n,m;
int dp[1100][1100];
int w[1100],v[1100];
int main()
{
memset(dp,0,sizeof(dp));
int n,m;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&w[i],&v[i]);
scanf("%d",&m);
for(int i=n-1;i>=0;i--)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k*w[i]<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i+1][j-k*w[i]]+k*v[i]);
}
}
}
printf("%d
",dp[0][m]);
return 0;
}
上面一种算法有三重循环，复杂度可能达到(n*m*m),这样并不够好，其实在这里有重复的计算
在dp[i+1][j]的计算中选择k(k>=1)个的情况，与在dp[i+1][j-w[i]]的计算中选择k-1个的情况是相同的，所以dp[i+1][j]的递推中k>=1部分的计算中已经在dp[i+1][j-w[i]]的计算中完成了。所以可以推出下列递推式
dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i])
所以有下列更高效的代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<set>
typedef long long ll;
using namespace std;
int n,m;
int dp[1100][1100];
int w[1100],v[1100];
int main()
{
memset(dp,0,sizeof(dp));
int n,m;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&w[i],&v[i]);
scanf("%d",&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<w[i])
dp[i+1][j]=dp[i][j];
else
dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
}
}
printf("%d
",dp[n][m]);
return 0;
}
题目链接：https://vjudge.net/contest/216347#problem/F
个人思路：刚刚开始学dp,写不太出来状态转移方程，知道这是完全背包，但是就是写不出来状态转移方程，后来搜了题解，
在这里dp[j],表示重量为j时最小价值，注意初始化dp[0]等于0,为什么呢，因为这是给所有dp计算的基础，刚开始当j-w[i]能减到0时，代表能整除，也就能赋值了
这样递归下去就是所求答案
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<set>
typedef long long ll;
using namespace std;
#define INF 1e9+7
int w[510],v[510];
int dp[10005];//dp[j]表示重量为j时，价值最小值
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int e,f,n,sum;
scanf("%d%d%d",&e,&f,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
sum=f-e;
fill(dp,dp+10000,INF);
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=w[i];j<=sum;j++)
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
}
if(dp[sum]==INF)
printf("This is impossible.
");
else
printf("The minimum amount of money in the piggy-bank is %d.
",dp[sum]);
}
return 0;
}