01背包问题报错,大佬求解惑
查看原帖
01背包问题报错,大佬求解惑
752826
JSJ_HuangYiXin楼主2023/8/29 14:51

为什么第二三重循环这样写不行,只有30分

#include<bits/stdc++.h>
using namespace std;

int dp[51][401][401];
int h[51],t[51],k[51];

int main()
{
    int H,T,n;  cin>>H>>T>>n;
    for(int i=1; i<=n; i++) cin>>h[i]>>t[i]>>k[i];
    
    for(int i=1; i<=n; i++)
        for(int j=h[i]; j<=H; j++)
            for(int z=t[i]; z<=T; z++)
                dp[i][j][z] = max(dp[i-1][j][z],dp[i-1][j-h[i]][z-t[i]]+k[i]);
                
    cout<<dp[n][H][T];
    
    return 0;
}

逆序遍历也一样

for(int i=1; i<=n; i++)
        for(int j=H; j>=h[i]; j--)
            for(int z=T; z>=t[i]; z--)
                dp[i][j][z] = max(dp[i-1][j][z],dp[i-1][j-h[i]][z-t[i]]+k[i]);
2023/8/29 14:51
加载中...