首页 > 代码库 > TYVJ1203
TYVJ1203
裸分组背包
v[i][j]第i组第j个的价值
w[i][j]第i组第j个的费用(其实w[i][j]=j)
dp[i][j]把前i组放包里能获得的最大价值
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i][k]]+v[i][k])
用一维的话就是
dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k])
dp目标 dp[Total_V]
注意背包容量循环一定在每组成员循环外面
背包九讲上可以说涵盖了所有的背包问题，就算没有，只要背包
九讲完全理解，碰上背包问题也不会出问题了。
还是要再多看几眼，应用的不是很熟练
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxv = 101; 8 const int maxn = 101; 9 int v[maxn],dp[maxv];10 int main()11 {12 int n,m;13 cin>>n>>m;14 memset(dp,0,sizeof(dp));15 for(int k = 1;k<=n;++k)16 {17 for(int i = 1;i<=m;++i)18 cin>>v[i];19 for(int j = m;j>=0;--j)20 for(int i = 1;i<=m;++i)21 if(j>=i)dp[j] = max(dp[j],dp[j-i]+v[i]);22 }23 printf("%d\n",dp[m]);24 return 0;25 }
TYVJ1203
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。