设f(i,x)表示前i件物品，背包容量为x时的最大价值，那么转移式可以表示为f(i,x)=max(f(i-1,x-w[i]+c[i]),f(i-1,x)),那么f(n,m)即为最优解。其实整体思想则表示为从容量为1的开始计算并且后面的计算不断的使用前面已经计算的值，这样就可以避免重复计算。
还有一道货币系统问题，即已知货币系统有v种面值，求组成面值N的货币有多少种方案？ 【样例输入】 3（v) 10(N) 1 2 5(各种面值大小) 【输出样例】 10 题解： 主要思想就是另创一个数组，每读入一种面值对其进行不断加，最后看数组下标为N的大小即为ans。让数组在循环体中滚动运算。 code
#include<iostream>#include<stdio.h>using namespace std;int f[1000];int main(void){ int v,n,p; cin>>v>>n; for(int i=1;i<=v;i++) { cin>>p; f[p]++; for(int j=p;j<=n;j++) //滚动计算 { f[j]+=f[j-p]; } } cout<<f[n]<<endl;}补上一次简单背包中的一题 数字分组 Ural 1005 将一组数分成两组，让他们的和之差最小，求最小值。 【输入样例】 5 1 2 3 4 5 【输出样例】 1 题解： 其实这题转换一下思路就可以化简为之前用过的装箱问题。即从n个物品中选若干个，求重量小于sum/2的最大值。 code
#include<iostream>#include<stdio.h>using namespace std;int f[1000],dp[1000];int main(void){ int n,sum=0,max; cin>>n; for(int i=1;i<=n;i++) { cin>>f[i]; sum+=f[i]; } max=sum/2; for(int i=1;i<=n;i++) { for(int j=max;j>=0;j--) //注意！这里要用倒序，不然会出现重复计算 { if(dp[j]) dp[j+f[i]]=1; } dp[f[i]]=1; } for(int i=max;i>=0;i--) { if(dp[i]) { cout<<sum-2*i<<endl; break; } }}最后是完全背包问题，其实如果0/1背包理解的话那这个就很好理解了 题目同0/1背包问题，唯一不同的地方是每种物品都有无限多个，求可以获得的最大值 题解： 因为0/1背包有个数限制所以for循环是按照物品来的，而该题没有这个限制故按照包的大小来计算 code:
#include<iostream>#include<stdio.h>using namespace std;int w[5000],c[5000],dp[5000]; int main(void){ int n,m,t; cin>>m>>n; for(int i=1;i<=n;i++) { cin>>w[i]>>c[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(i>=w[j]) { t=dp[i-w[j]]+c[j]; if(t>dp[i]) dp[i]=t; } } } cout<<dp[m]<<endl;}新闻热点
疑难解答
