好的 md这个编译器怎么用啊
好吧 今天复习了01背包 在不写下来就又忘了。。。。
果然嗷,《挑战程序设计竞赛》关于背包的引入我看的很棒,先记下来
最朴素的方法:
针对每个物品是否放入背包进行搜索试试看
int n,m; int weight[MAX],val[MAX]; int rec(int i,int j)//从第i个物品挑选总重小于j的部分 { int res; if(i==n) res=0;//已经没有剩余物体了 else if(weight[i]>j) res=rec(i+1,j);//选不了 else res=max(rec[i+1][j],rec[i+1][j-weight[i]]+val[i]);//要么选or不选 return res; } void solve() { printf("%d\n",rec(1,m)); }
最坏是O(2n);
递归的调用
然后可以用一个数组(二维)存放已经算过的,之后直接调用即可
不用函数,利用递推式,简单的二重循环
for(int i=n;i>=1;i--){ for(int j=0;j<=m;j++){ if(weight[i]>j) dp[i][j]=dp[i+1][j]; else dp[i][j]=max(dp[i+1][j],dp[i+1][j-weight[i]]+val[i]); } } printf("%d",dp[1][m]);
滚动数组
for(int i=n;i>=1;i--){ int res=i%2; int deta=(res%2==1)?-1:1; for(int j=0;j<=m;j++){ if(weight[i]>j) dp[res][j]=dp[res+deta][j]; else dp[res][j]=max(dp[res+deta][j],dp[res+deta][j-weight[i]]+val[i]); } } printf("%d",dp[1][m]);
没找到题目来测试,估计应该没有问题
明天的话,打算把怎么选的路径给学会,和一些经典DP像LCS啊之类的,
这样写太累了而且感觉没有效果,以后只写我难理解的,剩下的时间感觉可以拿去做题
希望有用吧,就算用这个时间去学常规,估计我也学不进去。