正文 

当前位置： 首页 > java > java教程

动态规划：背包问题

记性不好，多记记吧 记性不好，多记记吧     2022-08-08     567

关键词：

背包问题  

  • 有一个背包（限定条件：对可选的东西进行限制），从一堆物品中选择若干放进背包，使得最后背包中的价值是最大的
  • 01背包：对于一个物品，可以选0或1次    
  • 完全背包：对于一个物品，可以选多次(>=1)  

01背包 

1. 问题描述 http://hihocoder.com/problemset/problem/1038

有M张奖券，奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换且评分值为value(i)。每件奖品最多只能兑换一次。凭借他手上的M张奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。

奖品标号 1 ... i ... N
需要奖券 need(1) ... need(i) ... need(N)
评分值 value(1) ... value(i) ... value(N)

2. 状态转换

  • 状态：allValue[i][j] = 喜好总值[当前是第i件物品][前面已经使用的奖券j]
  • 决策：第i件物品是否要选
  • 状态转换: allValue[i][j] = max{allValue[i - 1][j], allValue[i - 1][j - need[i]] + value[i]}
  • 从左往右，从下往上 for(...i...){for(...j...)}

3. 代码

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<stdio.h>
 4 int dp[505][100005];
 5 int w[505],v[505];
 6 int max(int m,int n)
 7 {
 8     return m>n?m:n;
 9 }
10 void solve(int n,int m)
11 {
12     int i,j;
13     for(i=0;i<=m;i++)
14         dp[0][i]=0;
15     for(i=0; i<n; i++)
16         for(j=0; j<=m; j++)
17         {
18             if(j<w[i])
19                 dp[i+1][j]=dp[i][j];
20             else
21                 dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
22         }
23         printf("%d",dp[n][m]);
24 }
25 int main()
26 {
27     int n,m,i;
28     scanf("%d%d",&n,&m);
29     for(i=0;i<n;i++)
30             scanf("%d%d",&w[i],&v[i]);
31     solve(n,m);
32     return 0;
33 }
View Code

完全背包 

1. 问题描述 http://hihocoder.com/problemset/problem/1043

可以兑换无数次

2. 状态转换

  • 状态：allValue[i][j] = 喜好总值[当前是第i件物品][前面已经使用的奖券j]
  • 决策：第i件物品可以选k件(0<=k<=剩余的奖券/第i件物品需要的)
  • 状态转换: allValue[i][j] = max{allValue[i - 1][j - k*need[i]] + k*value[i]}
  • 优化转换关系:
    • 在对j的遍历过程中，会先后计算到allValue[i][j-need[i]], allValue[i][j]
    • 1) allValue[i][j] = max{allValue[i-1][j], allValue[i-1][j-need[i]] + value[i], ...,allValue[i-1][j-k*need[i]]+k*value[i]}
    • 2)allValue[i][j - need[i]] = max{allValue[i-1][j-need[i]] + value[i], ...,allValue[i-1][j-k'*need[i]]+k'*value[i]}
    • 1)2)可以转换成：allValue[i][j] = max{allValue[i-1][j], allValue[i][j - need[i]] + value[i]}

3. 代码

 1 #include <iostream>
 2 using namespace std;
 3 const int maxN = 501;
 4 const int maxM = 100001;
 5 int values[maxN][maxM];
 6 struct Prize
 7 {
 8     int need;
 9     int value;
10 }prizes[maxN];
11 
12 
13 void dp(int N, int M)
14 {
15     for (int i = 0; i <= M; i++)
16         if (i >= prizes[0].need)
17             values[0][i] = i / prizes[0].need * prizes[0].value;
18         else
19             values[0][i] = 0;
20     int max = 0;
21     for (int i = 1; i < N; i++)
22     {
23         for (int j = 0; j <= M; j++)
24         {
25             if (prizes[i].need > j)
26                 values[i][j] = values[i - 1][j];
27             else
28             {
29                 int tmp = values[i][j - prizes[i].need] + prizes[i].value;
30                 if (tmp > values[i - 1][j])
31                     values[i][j] = tmp;
32                 else
33                     values[i][j] = values[i - 1][j];
34             }
35         }
36     }
37 }
38 
39 int main()
40 {
41     int M, N;
42     cin >> N >> M;
43     for (int i = 0; i < N; i++)
44         cin >> prizes[i].need >> prizes[i].value;
45     prizes[N].need = prizes[N].value = 0;
46     
47     dp(N, M);    
48     cout << values[N - 1][M] << endl;
49     return 0;
50 }
View Code

用动态规划求解分数背包问题

】用动态规划求解分数背包问题【英文标题】：Solvingfractionalknapsackproblemwithdynamicprogramming【发布时间】：2020-06-0417:12:17【问题描述】：前几天，我在阅读关于分数背包问题的贪心算法和动态规划的文章，我看到这个问题可以用贪... 查看详情

10.动态规划——0-1背包问题

　　在上一篇《9.动态规划（2）——子集和问题》中，谈到了什么是子集和问题，以及实现。背包问题实际也是子集和问题的一种，不过背包问题不是“判断问题”而是一个“最优问题”。而背包问题实际上又... 查看详情

动态规划：背包问题

背包问题 有一个背包（限定条件：对可选的东西进行限制），从一堆物品中选择若干放进背包，使得最后背包中的价值是最大的01背包：对于一个物品，可以选0或1次  完全背包：对于一个物品，可以选多次(>=1) ... 查看详情

动态规划/背包问题背包问题第一阶段最终章：混合背包问题

前言今天是我们讲解动态规划专题中的「背包问题」的第十一篇。今天将会学习「混合背包」问题，同时也是我们「背包问题」的第一阶段的最后一节。今天首先会和大家回顾之前学过的三种背包问题。然后通过一道「混合背包... 查看详情

动态规划-背包问题(代码片段)

...为“无界背包或完全背包”问题。一、0-1背包问题可以用动态规划来解决背包问题。以0-1背 查看详情

算法图解-动态规划

内容：动态规划，它将问题分成小问题，并先着手解决这些小问题学习如何设计问题的动态规划解决方案9.1背包问题　　如何让背包内装的商品价值最高？如果尝试所有的可能性，运行时间为O(2n)。9.2背包问题FAQ　　9.2.7处理相... 查看详情

动态规划-第二节：动态规划之背包类型问题(代码片段)

文章目录一：01背包问题（1）题目描述（2）解题思路（3）完整代码二：分割等和子集（01背包变形）（1）题目描述（2）解题思路（3）完整代码三：完全背包问题&... 查看详情

动态规划与背包问题(代码片段)

动态规划与背包问题  应用场景-背包问题物品重量价格吉他(G)11500音响(S)43000电脑(L)32000 背包问题：有一个背包，容量为4磅，现有如下物品要求达到的目标为装入的背包的总价值最大，并且重量不超出要求装入的物品... 查看详情

背包动态规划

】背包动态规划【英文标题】：KnapsackDynamicProgramming【发布时间】：2012-04-1707:51:08【问题描述】：这是一个典型的背包问题，需要动态规划，并且对物品的供应没有限制。我一直在为我的班级研究这个，我尝试了几个小时的算法... 查看详情

动态规划背包问题

...最长递增（减）序列长度等等。背包问题变体很多。　　动态规划问题实际上与备忘录式深搜有些类似。1.0-1背包题目：　　有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值... 查看详情

基础算法——动态规划0/1背包问题

　　首先，对于动态规划，我来做一个简短的介绍，相信各位都看得懂。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。先给一道最简单的例题（小学奥数水平）： 这就是一... 查看详情

动态规划解决背包问题(代码片段)

...音响价格3000或者装吉他和电脑价值3500这道题我们可以用动态规划算法来解决动态规划算法介绍：1.动态规划算法的核心思想是&#x 查看详情

动态规划算法实现部分——0/1背包问题

代码：importjava.util.*;importjava.util.Scanner;/**动态规划思想解决0/1背包问题*/publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);System.out.println("输入背包的容量");intbagCap=in.nextInt() 查看详情

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

1.poj1742DescriptionPeopleinSilverlandusecoins.TheyhavecoinsofvalueA1,A2,A3...AnSilverlanddollar.OnedayTonyopenedhismoney-boxandfoundthereweresomecoins.Hedecidedtobuyaverynicewatchinanearbyshop.Hewant 查看详情

从01背包问题理解动态规划---初体验

　　这个问题有两种解法，动态规划和贪婪算法。本文仅涉及动态规划。　　先不套用动态规划的具体定义，试着想，碰见这种题目，怎么解决?　　首先想到的，一般是穷举法，一个一个地试，对于数目小的例子适用，如果容... 查看详情

01背包和动态规划

　　做了一段时间ＮＯＩ，做到动态规划看了几天算法书籍。还是没有深入，学了基本的动态规划，稍有一点体会，记录到这里。　　背包是这样一类问题：在限定总质量前提下，从若干质量＼价格对中，取哪些能使得价格最大... 查看详情

动态规划——背包问题(代码片段)

...析最基础的方法是枚举，但时间复杂度为O(22)O(2^2)O(22)动态规划的可以将时间复杂度降为O(nm)O(nm 查看详情

0-1背包问题_动态规划(代码片段)

...sp;普通背包问题可以用贪心来解决，而0-1背包问题只能靠动态规划来做，而且在我们平时的做题中经常会遇到0-1背包问题的变形，所以有必要牢牢掌握0-1背包问题的思想和解题思路。根据下面的图更可以找到应该选那些背包下面... 查看详情