背包问题，动态规划

左手的ㄟ右手 2022-02-28 14:50 299阅读 0赞

将下面四个重量的物品1，2，2，3 价值分别是9，3，3，6 装进 重量为4的背包中，使得背包的重量不超过4，并且价值最大。

#include<iostream>
    #include<cstring>
    #include<map>
    #include <vector>
    #include <set>
    #include <algorithm>
    #include<limits.h>
    
    using namespace std;
    bool camp(vector<int>&a,vector<int>&b){
    
        return a[1]<= b[1]? (a[1]==b[1]? a[0]<b[0]:true) : false;
    }
    int main(){
    
        vector<int> weights={0,1,2,2,3};
        vector<int> value={0,9,3,3,6};
        vector<vector<int>> v(5,vector<int>(5,0));
        int n=4;
        int m=4;
        for(int i=1;i<=n;i++){
    
            for(int j=1;j<=m;j++){
    
                if(weights[i]>j){
                    v[i][j]=v[i-1][j];
                }else{
    
                    int v1=v[i-1][j];
    
                    int v2=v[i-1][j-weights[i]]+value[i];
    
                    v[i][j]=max(v1,v2);
    
    
                }
    
    
            }
    
        }
    
    
        cout<<v[4][4]<<endl;
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，299人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-背包问题

动态规划--背包问题

悠悠/ 2024年04月23日 20:02/ 0 赞/ 84 阅读

相关背包问题-动态规划

[背包问题九讲][Link 1] [背包问题参考博客][Link 2] 文章目录介绍: 背包问题 01背包问题

逃离我推掉我的手/ 2023年08月17日 17:42/ 0 赞/ 114 阅读

相关动态规划——背包问题

背包问题 -------------------- 目录 1. 概述 2. 背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个

叁歲伎倆/ 2023年06月30日 08:58/ 0 赞/ 66 阅读

相关背包型动态规划——背包问题6

给出一个都是正整数的数组 `nums`，其中没有重复的数。从中找出所有的和为 `target` 的组合个数。示例：输入: nums = [1, 2, 4

阳光穿透心脏的1/2处/ 2022年10月27日 12:06/ 0 赞/ 165 阅读

相关背包型动态规划——背包问题3

给定 `n` 种物品, 每种物品都有无限个. 第 `i` 个物品的体积为 `A[i]`, 价值为 `V[i]`. 再给定一个容量为 `m` 的背包. 问可以装入背包的

傷城~/ 2022年10月27日 12:06/ 0 赞/ 176 阅读

相关背包型动态规划——背包问题5

给出 n 个物品, 以及一个数组, `nums[i]` 代表第i个物品的大小, 保证大小均为正数, 正整数 `target` 表示背包的大小, 找到能填满背包的方案数。

素颜马尾好姑娘i/ 2022年10月27日 12:06/ 0 赞/ 186 阅读

相关背包型动态规划——背包问题1

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\] 示例：样例 1: 输入: [3,4,8,5]

旧城等待，/ 2022年10月27日 06:30/ 0 赞/ 156 阅读

相关背包型动态规划——背包问题2

有 `n` 个物品和一个大小为 `m` 的背包. 给定数组 `A` 表示每个物品的大小和数组 `V` 表示每个物品的价值. 问最多能装入背包的总价值是多大? 样例

忘是亡心i/ 2022年10月27日 06:29/ 0 赞/ 156 阅读

相关背包问题，动态规划

将下面四个重量的物品1，2，2，3 价值分别是9，3，3，6 装进重量为4的背包中，使得背包的重量不超过4，并且价值最大。 include<iostream>

左手的ㄟ右手/ 2022年02月28日 14:50/ 0 赞/ 300 阅读

相关动态规划背包问题

[本篇博文参考此博文，该博文PPT非常有助理解][PPT] > 问题描述： > 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背

傷城~/ 2021年09月11日 08:42/ 0 赞/ 425 阅读