hdu--1712--分组背包<如果你真的明白了背包..>

真的是蛮好的一题~

里面的第二层循环 小变量 i j k分别从哪里开始 哪里结束 逆序 还是 顺序 都要好好地去体会

我自己讲不来  至于为什么V是逆序 你可以将它当成某种特殊的01背包来看待 就很容易想了

其实 第3层循环

                for( int k = 1 ; k<=m ; k++ )
                {
                    if( j>=k )
                    {
                        dp[j] = max( dp[j] , dp[j-k]+a[i][k-1] );
                    }
                }

这里的 if( j>=k )因为是K就代表了天数 这是很巧合情况不用开数组  一般的话 要开个vol[ k ]数组

这边的话 也是有 滚动数组的压缩空间概念在的

不然的话 是开个二维dp[i][j] i就代表到了第I组物品  J代表前I组所占用的体积 DP数组就代表前I组占用J的体积所能得到的最大价值

好了 上代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int size = 110;
int a[size][size];
int dp[size];

int main()
{
    cin.sync_with_stdio(false);
    int t , n , m;
    while( cin >> n >> m && (n||m) )
    {
        for( int i = 0 ; i<n ; i++ )
        {
            for( int j = 0  ; j<m ; j++ )
            {
                cin >> a[i][j];
            }
            //a[i][m] = 0;
        }
        memset( dp , 0 , sizeof(dp) );
        for( int i = 0 ; i<n ; i++ )
        {
            for( int j = m ; j>=1 ; j-- )
            {
                for( int k = 1 ; k<=m ; k++ )
                {
                    if( j>=k )
                    {
                        dp[j] = max( dp[j] , dp[j-k]+a[i][k-1] );
                    }
                }
            }
        }
        cout << dp[m] << endl;
    }
    return 0;
}

today:

　　该认真的时候

　　认真点

　　认真是种情怀