首页 > 代码库 > 01背包基础 (杭电2602)
01背包基础 (杭电2602)
01背包问题:
有一个体积为V的背包,有n件物品,每件物品的体积,价值分别为w[i],p[i];要从n件物品中选些放入背包中,使背包里物品的总价值最大。
动态方程:c[i][j]=max(c[i-1][j],c[i-1][j-w[i]]+p[i]).
有关动态方程方面的代码:
for (int i = 1; i <= n; i++) { for (int j = 1; j <= total_weight; j++) { if (w[i] > j) { c[i][j] = c[i-1][j]; } else { //也可以用<span style="font-family: KaiTi_GB2312;font-size:18px;">c[i][j]=max(c[i-1][j],c[i-1][j-w[i]]+p[i])代替下面的</span> if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) { c[i][j] = c[i-1][j]; } else { c[i][j] = v[i] + c[i-1][j-w[i]]; } } } }在杭电2602中我们就可以很舒服的用01背包解决:
题目网址:http://acm.hdu.edu.cn/showproblem.php?pid=2602
初学者代码:
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int c[1011][1011]; int max(int a,int b) { return a>b?a:b; } int knapsack(int m,int n) { memset(c,0,sizeof(c)); int i,j,val[1001],V[1001]; for(i=1;i<=n;i++) scanf("%d",&val[i]); for(i=1;i<=n;i++) scanf("%d",&V[i]); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (V[i] > j) { c[i][j] = c[i-1][j]; } else { c[i][j]=max(c[i-1][j],c[i-1][j-V[i]]+val[i]); } } } return (c[n][m]); } int main() { int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); printf("%d\n",knapsack(m,n)); } return 0; }
这个问题代码需要优化,减少时间空间复杂度,
(优化后代码)AC代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int c[1011]; int max(int a,int b) { return a>b?a:b; } int knapsack(int m,int n) { memset(c,0,sizeof(c)); int i,j,val[1001],V[1001]; for(i=1;i<n+1;i++) scanf("%d",&val[i]); for(i=1;i<n+1;i++) scanf("%d",&V[i]); for(i=1;i<n+1;i++) for(j=m;j>=V[i];j--) c[j]=max(c[j-V[i]]+val[i],c[j]); return(c[m]); } int main() { int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); printf("%d\n",knapsack(m,n)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。