首页 > 代码库 > hdu--1712--分组背包<如果你真的明白了背包..>
hdu--1712--分组背包<如果你真的明白了背包..>
真的是蛮好的一题~
里面的第二层循环 小变量 i j k分别从哪里开始 哪里结束 逆序 还是 顺序 都要好好地去体会
我自己讲不来 至于为什么V是逆序 你可以将它当成某种特殊的01背包来看待 就很容易想了
其实 第3层循环
1 for( int k = 1 ; k<=m ; k++ )2 {3 if( j>=k )4 {5 dp[j] = max( dp[j] , dp[j-k]+a[i][k-1] );6 }7 }
这里的 if( j>=k )因为是K就代表了天数 这是很巧合情况不用开数组 一般的话 要开个vol[ k ]数组
这边的话 也是有 滚动数组的压缩空间概念在的
不然的话 是开个二维dp[i][j] i就代表到了第I组物品 J代表前I组所占用的体积 DP数组就代表前I组占用J的体积所能得到的最大价值
好了 上代码
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 110; 7 int a[size][size]; 8 int dp[size]; 9 10 int main()11 {12 cin.sync_with_stdio(false);13 int t , n , m;14 while( cin >> n >> m && (n||m) )15 {16 for( int i = 0 ; i<n ; i++ )17 {18 for( int j = 0 ; j<m ; j++ )19 {20 cin >> a[i][j];21 }22 //a[i][m] = 0;23 }24 memset( dp , 0 , sizeof(dp) );25 for( int i = 0 ; i<n ; i++ )26 {27 for( int j = m ; j>=1 ; j-- )28 {29 for( int k = 1 ; k<=m ; k++ )30 {31 if( j>=k )32 {33 dp[j] = max( dp[j] , dp[j-k]+a[i][k-1] );34 }35 }36 }37 }38 cout << dp[m] << endl;39 }40 return 0;41 }
today:
该认真的时候
认真点
认真是种情怀
hdu--1712--分组背包<如果你真的明白了背包..>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。