划地课堂 2021-12-25 12:04 采纳率: 0%
浏览 36

动态规划中逆序循环和顺序循环结果不一样,不知道什么原因,能不能解答一下?


#include<algorithm>
#include<iostream>
const int maxn = 6005;
using namespace std;
int w[maxn],c[maxn],s[maxn],f[maxn];
int main(){
    int n,m;
    cin>>n>>m;//奖品的种数,拨款金额 
    for(int i=1;i<=n;i++)  cin>>w[i]>>c[i]>>s[i];//第i种奖品价格,价值,最多购买的数量 
    //f[j]表示计划j元买奖品实现最大价值 
    for(int i=1;i<=n;i++){//从前i种奖品中挑选奖品放入背包 
        for(int j=0;j<=m;j++){//背包中奖品总价格为j 【逆序输出正确答案1040,顺序输出错误答案1650,望指点】
            for(int k=0;k<=s[i];k++){//其中背包中第i种奖品数量为k 
                if(j-k*w[i]>=0)//只有k个第i种奖品总价值小于或等于j元,k个第i种奖品才能放入背包 
                    f[j] = max(f[j],f[j-k*w[i]]+k*c[i]);
                //计划j元买奖品实现的最大价值=k个第i种奖品的总价值+计划j-k*w[i]元买奖品实现的最大价值 
            }
        }
    }
    cout<<f[m];
    return 0;
}
  • 写回答

1条回答 默认 最新

  • CSDN专家-link 2021-12-25 12:10
    关注

    逆序你是咋写的呢?

    评论

报告相同问题?

问题事件

  • 创建了问题 12月25日

悬赏问题

  • ¥20 win11修改中文用户名路径
  • ¥15 win2012磁盘空间不足,c盘正常,d盘无法写入
  • ¥15 用土力学知识进行土坡稳定性分析与挡土墙设计
  • ¥70 PlayWright在Java上连接CDP关联本地Chrome启动失败,貌似是Windows端口转发问题
  • ¥15 帮我写一个c++工程
  • ¥30 Eclipse官网打不开,官网首页进不去,显示无法访问此页面,求解决方法
  • ¥15 关于smbclient 库的使用
  • ¥15 微信小程序协议怎么写
  • ¥15 c语言怎么用printf(“\b \b”)与getch()实现黑框里写入与删除?
  • ¥20 怎么用dlib库的算法识别小麦病虫害