01背包问题(动态规划求解)

Wesley13
• 阅读 354

这两天c++的习题开始不考察c++了,开始考察动态规划问题,唉,没学过动态规划算法来编这题目真是一把辛酸泪,下面给出题目(题目来源:郭玮老师的mooc
2:Charm Bracelet
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
输入
Line 1: Two space-separated integers: N and M
Lines 2…N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
输出
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23
看上去这题确实不难,真正的题目就是给定总重量m,求最大的desirability。然后我一下子想到只要遍历一下所有情况,然后取出weight满足的情况中desirability最大的即可,贴出我写的代码:

#include <iostream>
#include <cstring>
#define MAX 3402
using namespace std;

class charm;
int combine_decrease(int m , charm* arr, int start, int* result, int count, const int NUM);

class charm
{
public:
    int w;
    int d;
};


int main (void)
{
    int n;
    int m;
    int i;
    int j ;
    int max_desir = 0;
    int temp = 0;
    charm charm_list[MAX] ; 
    int result[MAX] ;
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>charm_list[i].w>>charm_list[i].d;
    }//have stored the charm;
    for(i = 1;i <= n; ++i){
        temp = combine_decrease(m,charm_list , n , result , i , i );
        if (temp >= max_desir)
            max_desir = temp;
    }
    cout<<max_desir;

}


//arr涓哄師濮嬫暟缁?
//start涓洪亶鍘嗚捣濮嬩綅缃?
//result淇濆瓨缁撴灉锛屼负涓€缁存暟缁?
//count涓簉esult鏁扮粍鐨勭储寮曞€硷紝璧疯緟鍔╀綔鐢?
//NUM涓鸿閫夊彇鐨勫厓绱犱釜鏁?
int combine_decrease(int m, charm* arr, int start, int* result, int count, const int NUM)
{
  int i;
  int sum = 0;
  int temp = 0;
  int temp_weight = 0; 
  for (i = start; i >=count; i--)
  {
    result[count - 1] = i - 1;
    if (count > 1)
    {
      temp = combine_decrease(m,arr, i - 1, result, count - 1, NUM);
      if(temp >= sum){
        sum = temp;
      }
      temp = 0;
    }
    else
    {
        int j;
        for (j = NUM - 1; j >=0; j--){
            temp_weight +=arr[result[j]].w;
            temp += arr[result[j]].d;
            //printf("%d ",arr[result[j]].d);;
            if(temp_weight > m) break;
        }
        //cout<<endl;
        //cout<<"desire:"<<temp<<"weight:"<<temp_weight<<endl;
        if(temp>=sum && temp_weight <= m)
            sum = temp;
        //cout<<"sum:"<<sum<<endl;
        temp = 0;
        temp_weight = 0;
    }
  }
  return sum;
}

答案确实是做出来了,应该也是对的,然后提交后出现**“超时”**,唉想想也是,遍历所有情况,想想都害怕,还用递归来实现,机子肯定要爆掉。没办法实在想不出,上网查资料。
一查就查到了,这是经典的01背包问题,也就是经典的动态规划求解问题:
代码来源https://blog.csdn.net/qingboda110/article/details/51050299

#include<stdio.h>
int W[3500];
int D[3500];
int f[13000];
int main(){
    int ans,max,n,i,j;
    scanf("%d",&n);
    scanf("%d",&max);
    for(i=0;i<n;i++){
        scanf("%d",&W[i]);
        scanf("%d",&D[i]);
    }
    for(i=0;i<n;i++){
        for(j=max;j>0;j--){
            if(j>=W[i]&&f[j]<f[j-W[i]]+D[i])
                f[j]=f[j-W[i]]+D[i];
        }
    }
    ans=0;
    for(i=0;i<=max;i++){
        if(f[i]>ans)
            ans=f[i];
    }
    printf("%d\n",ans);
    return 0;
}

一提交果然成功,但是看着代码依然无法理解,继续查资料,发现了这篇博文,讲的很好,看了半小时终于搞懂了,01背包问题,给出博文地址https://www.cnblogs.com/wujing-hubei/p/6376218.html?utm_source=tuicool&utm_medium=referral
动态规划的思路,还是用小问题的解决去解决大问题,然后关键就在于找到大问题到小问题的简化关系:
01背包问题(动态规划求解)
在此谢过博主的帮助了。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Kubrnete Kubrnete
3年前
初步了解01背包问题(分治篇)
目录问题描述(问题描述)输入格式(输入格式)输出格式(输出格式)基于0/1背包的迭代算法(基于01背包的动态规划算法)0/1背包问题的分析(01背包问题的分析)分治法(分治法)总结(总结)问题描述Coda非常喜欢玩“NewWorldOnline”,受到某部动画的影响,他
Kubrnete Kubrnete
3年前
完全背包问题
问题描述有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v\i\,体积为w\i\,求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可
Kubrnete Kubrnete
3年前
基于01背包问题的动态规划算法
目录初步认识动态规划(初步认识动态规划)与动态规划有关的理论知识:(与动态规划有关的理论知识:)动态规划中的最优决策表(基于填表的动态规划算法)最终版动态规划(最终版动态规划)总结(总结:)初步认识动态规划动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推
Wesley13 Wesley13
2年前
Java日期时间API系列31
  时间戳是指格林威治时间1970年01月01日00时00分00秒起至现在的总毫秒数,是所有时间的基础,其他时间可以通过时间戳转换得到。Java中本来已经有相关获取时间戳的方法,Java8后增加新的类Instant等专用于处理时间戳问题。 1获取时间戳的方法和性能对比1.1获取时间戳方法Java8以前
Stella981 Stella981
2年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Stella981 Stella981
2年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Wesley13 Wesley13
2年前
360笔试
/序列重组时间限制:C/C语言1000MS;其他语言3000MS内存限制:C/C语言65536KB;其他语言589824KB题目描述:在一个古老的国度,这个国家的人并不懂得进位,但是对取模情有独钟,因此诞生了一个经典的问题,给出两个在m进制下含有n位的数字,你可以分别将这两个数各位上的数字重新排列,然
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
3个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这