装箱问题(NOIP2001&水题测试2017082401)

题目链接：装箱问题

这题经典的01背包。

动规。

设计状态f[n][V]表示前n个物体放在V中的最大体积是多少。

所以代码如下：

#include<bits/stdc++.h>

using namespace std;

int f[35][20003];

int dp(int* v,int V,int n){

    if(f[n][V]>0){

        return f[n][V];

    }

    if(n==0){

        return 0;

    }

    if(V>=v[n-1]){

        f[n][V]=max(dp(v,V,n-1),dp(v,V-v[n-1],n-1)+v[n-1]);

    }else{

        f[n][V]=dp(v,V,n-1);

    }

    return f[n][V];

}

int main(){

    int V,n;

    memset(f,-1,sizeof(f));

    scanf("%d%d",&V,&n);

    int v[n];

    for(int i=0;i<n;i++){

        scanf("%d",&v[i]);

    }

    printf("%d",V-dp(v,V,n));             //1

    return 0;

}

1处：这里要注意一下，我们求出的动规结果是占用体积最大值，所以要拿总体积减一下。

巴特西

装箱问题(NOIP2001&水题测试2017082401)

最新文章

热门文章