记忆化·搜索 求大佬帮助

回复帖子

@2311241987j 2018-11-07 20:09 回复
#include<bits/stdc++.h>
using namespace std;
int f[3505];
int c[3505];
int w[3505];
int t;
bool flag[3505];
int dfs(int kg) {
    int u=0;
    if(f[kg]!=-1)return f[kg];
    for(int i=1; i<=t; i++)
        if(!flag[i])
            if(c[i]<=kg) {
                flag[i]=1;
                u=max(u,dfs(kg-c[i])+w[i]);
                flag[i]=0;
            }
    return f[kg]=u;
}
int main() {
    int m;
    cin>>t>>m;
    memset(f,-1,sizeof(f));
    for(int i=1; i<=t; i++)
        cin>>c[i]>>w[i];
    cout<<dfs(m);
}/*
4 6
1 4
2 6
3 12
2 7*/

这个是记忆化搜索的思路,但是有重复选择的问题,是因为它return的f[kg]加上另一个f[]会出现重复的情况,所以不知道改正,求指点。

@Sagittarius 2018-11-07 20:48 回复 举报

想到一个不太优越的方法,状态开二维$f[i][j]$表示用了i的重量,上一个选的是j的最大价值。但是这样会爆空间orz

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



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