hdu 3496 Watch The Movie(二维01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=3496

刚看了背包九讲二维费用的背包。看到这个题，感觉像二维01背包。这里有两个限制条件，一个是件数，一个是容量。其中件数必须是m件。因为初始化的问题WA了N次。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[110][1010];
int main()
{
    int test;
    int n,m,l,c[110],w[110];
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d %d",&n,&m,&l);
        for(int i = 1; i <= n; i++)
            scanf("%d %d",&c[i],&w[i]);

        for(int i = 0; i <= m; i++)
        {
            for(int j = 0; j <= l; j++)
            {
                if(i == 0)
                    dp[i][j] = 0;       //注意初始化
                else dp[i][j] = -INF;
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = m; j >= 1; j--)
            {
                for(int k = l; k >= c[i]; k--)
                    dp[j][k] = max(dp[j][k],dp[j-1][k-c[i]]+w[i]);
            }
        }
        if(dp[m][l]>0) printf("%d\n",dp[m][l]);
        else printf("0\n");
    }
    return 0;
}

hdu 3496 Watch The Movie(二维01背包),布布扣,bubuko.com

hdu 3496 Watch The Movie(二维01背包)

原文：http://blog.csdn.net/u013081425/article/details/20227121