求助

回复帖子

@黑猫_琉璃 2018-11-15 00:24 回复

不好意思深夜打扰了。

没有过样例,代码如下:

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

int n,v,know[1300005];
bool knowed[1300005] = {false};

struct things{
    int wgt;
    int val;
    int num;
}thi[3410];

//快排比较函数
bool cmp(const things &a,const things &b){
    return (a.wgt <= b.wgt);
} 
//递归函数(参数:当前容量)
long long int rec(int crtv){
    //边界
    if(crtv < thi[1].wgt){
        //当前背包容量比最小的东西的重量还要小,根本不可能塞东西 
        return 0; 
    }else if(crtv == thi[1].wgt){
        return thi[1].val; 
    }
    //记忆化搜索
    if(knowed[crtv]){
        return know[crtv];
    } 
    long long int maxn = 0;
    //遍历所有东西的重量,找到可能的价值最大值
    for(int i=1;i<=n;i++){
        if(thi[i].wgt > crtv){
            break;
        }
        maxn = max(maxn,rec(crtv - thi[i].wgt) + thi[i].val);
    } 
    know[crtv] = maxn;
    knowed[crtv] = true;
    //调试代码 
    cout<<crtv<<':'<<know[crtv]<<endl;
    return maxn;
}

int main(void){
    //得到物品的数量和背包的容量
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&thi[i].wgt,&thi[i].val);
        thi[i].num = i; 
    }
    //对物品对象按照重量从小到大快排
    sort(thi+1,thi+n+1,cmp);
    //输出
    printf("%lld",rec(v)); 
    return 0;
}

输入

4 6
1 4
2 6
3 12
2 7

输出

2:8
3:12
4:16
5:20
6:24
24

我观察调试代码后发现我的代码问题是可能会出现重复选择同一个物品的情况,我的思路是声明一个used数组来保存1300000种状态下的3410个物品的使用情况,但这样明显会MLE,求问如何优化啊?亦或是我的状态有问题?(本人刚学DP,实在想不出来更好的状态了)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。