首页 > 其他分享 >unbounded knapsack problem

unbounded knapsack problem

时间:2023-06-14 10:56:00浏览次数:46  
标签:unbounded volume item loop knapsack problem change dp

Description

Unbounded Knapsack Problem

There are $N$ kinds of items and a knapsack with the capacity of $V$, each item has unlimited pieces available.

The volume of the $i$-th item is $v_i$, and value is $w_i$. Please solve which items can be put into the pack so that the value is the greatest and the total volume of these items dosen't exceed the capacity of the pack.

Solution

It's a classic problem of dynamic programming and knapsack problem. We can solve the problem in two ways.

Create a new inner loop

For 01-pack-problem, each item can be used only once, while for UKP, we just need to add another layer of loops to the inner loop about volume, enumerating how many items $i$ are used in total.

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        for (k = 1; k * v[i] <= j; k++) {
            dp[j] = max(dp[j], dp[j - k * v[i] + k * w[i]);
        }
    }
}

Change traversing direction

For 01-pack-problem, the inner loop about volume, is from large to small. This is to ensure that when dp[j - v[i] + w[i] is compared with dp[j], the value used is the same as that in last loop.

While in UKP, the inner loop about volume, we can just change it to "from small to large", then in dp = max(dp[j], dp[j - v[i] + w[i]]), the value of dp[j - v[i]] + w[i] is that in current loop. While in i loop, dp[j - v[i]] = max(dp[j - v[i]], dp[(j - v[i]) - v[i]] + w[i]), in descending order, we can always find the maximum value: dp[j - k * v[i]] + k * w[i]($k$ could be 0).

Actually, in inner loop about volume, traversing from large to small ensures that each item can be used only once, while traversing from small to large ensures that each item can be used unlimitedly.

for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

Examples

标签:unbounded,volume,item,loop,knapsack,problem,change,dp
From: https://www.cnblogs.com/zwyyy456/p/17479577.html

相关文章

  • 5、题目:Training in Creative Problem Solving: Effects on Ideation and Problem Fin
    期刊信息(1)作者:GeorgeB.Graen,StephenG.Graen(2)期刊:OrganizationalBehaviorandHumanPerformance(3)DOI:10.1016/0030-5073(82)90233-1(4)ISSN:0030-5073   研究背景创造力训练作为工业培训的一个子集,普遍面临着工业培训研究的许多问题,也面临着一些独特的问题。......
  • 【每日一题】Problem 120F. Spiders
    原题解决思路通过给定的数据,将其构建称树,取其中最大的深度进行拼接,最后得到最终结果如何获取最大的深度以每个节点作为root构建树,然后取其中最大的深度#include<bits/stdc++.h>/***@paramvec*@paramcur当前节点*@paramlast上一个访问的节点*@param......
  • RTFM、STFW 和 X-Y Problem
    如何提问艾瑞克。史蒂文.雷蒙德(EricStevenRaymond)的提问的智慧。这是一篇长文,看完需要十几分钟的时间。如果之前没有认真看过并且思考过,这十几分钟会改变你的职业生涯。这文章可能会出现一些让人不适的词语或者过时的例子,但我认为这不会影响它要表达的内容,而你需要好好琢磨作......
  • 解决 This is probably not a problem with npm. There is likely additional logging
    在执行npmrunserve运行项目的时候报错:dengzemiaodeMacBook-Pro:lianshan_vuedengzemiao$npmrunserve......npmERR!codeELIFECYCLEnpmERR!errno1npmERR!lianshan@2.0.0serve:`vue-cli-serviceserve`npmERR!Exitstatus1npmERR!npmERR!Failedatthelia......
  • Not Another Linear Algebra Problem 题解
    题意:自己看。首先我们知道我们唯一能找到的题解在hos_lyric的代码里。把它放在这里:(由bikuhiku提供)\[\begin{aligned}&U\subseteq\mathbb{F}_p^n,\text{subspace}\\&a(U):=\#\{p\in\text{Aut}(\mathbb{F}_p^n)|\text{Ker}(p-\text{id})=U\}\\&b(U):=......
  • 【每日一题】Problem 44E. Anfisa the Monkey
    原题解决思路由题意可得\(ak\lesize\lebk\),因此当条件不符合该要求时即可退出因为\(size\lebk\),因此,我们可以假设每行都是\(b\)长度来满足条件二,因此第\(i\)行的长度为\(len=size-(k-i)b\),然后对\(len\)取与\(a\)中的较大者来满足条件一注意,如果后续行每......
  • 【每日一题】Problem 363B. Fence
    原题解决思路求k个木板的最小高度和,因为所有木板的高度和不超过1e9,因此计算出到当前木板j的总高度-前j-k模板的总高度并求得最小数即可#include<bits/stdc++.h>intmain(){intn,k;std::cin>>n>>k;std::vector<int>vec(n+1,0);for(in......
  • 【每日一题】Problem 331C1. The Great Julya Calendar
    原题解决思路寻求减到0所需的最小次数,即\(Num(n)\RightarrowNum(n-x)+1\)当存在一个x使得(n-x)%10=0时,那么(n-x)到下一次个位为0时至少需要两次,即该过程至少需要3次如果存在一个x'>x,那么上述过程可以简化到至少需要2次一般情况下,当n中的前面一段(百位......
  • 【每日一题】Problem 327A - Flipping Game
    原题解决思路计算数字"1"的最大数目,可以转换成计算数组最大和,即求\(maxSum(oldArraySum-(1\rightarrow0)+(0\rightarrow1))\RightarrowoldArraySum+maxSum(flipSum)\)误区注意:题目要求必须执行一次,因此起始值不是0而是-1#include<bits/stdc++.h>intm......
  • yum源使用报错-RockyLInux8.7-Modular dependency problem:
    报错信息如下:Kubernetes11kB/s|173kB00:15Modulardependencyproblem:Problem:conflic......