01背包问题

淩亂°似流年 2022-06-08 03:59 239阅读 0赞

### 【例9.11】01背包问题 ###

时间限制: 1000 ms 内存限制: 65536 KB

### 【题目描述】 ###

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。

### 【输入】 ###

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；

第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

### 【输出】 ###

仅一行，一个数，表示最大总价值。

### 【输入样例】 ###

10 4
    2 1
    3 3
    4 5
    7 9

### 【输出样例】 ###

12

### 【来源】 ###

[No][]

【解析】：

设状态：f\[i\]\[v\]表示前i件物品，重量不超过v的最大总价值

初始状态：f\[i\]\[v\]=0;

最终状态：f\[n\]\[m\]表示前n件物品，重量不超过m的最大总价值

状态转移方程：f\[i\]\[v\]=f\[i-1\]\[v\]表示不将第i件物品放入背包中的最大总价值

f\[i\]\[v\]=f\[i-1\]\[v-w\[i\]\]+c\[i\]表示将第i件物品放入背包中的最大总价值

因此：状态转移方程为f\[i\]\[v\]=max(f\[i-1\]\[v\],f\[i-1\]\[v-w\[i\]+c\[i\])

#include<iostream>
    using namespace std;
    int f[40][210];//f[i][v]表示前i件物品，重量不超过v的最大总价值 
    int w[40],c[40];
    int main()
    {
    	int m,n;
    	cin>>m>>n;
    	for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
    	for(int i=1;i<=n;i++)
    	{
    		for(int v=m;v>0;v--)
    		{
    			if(w[i]>v) f[i][v]=f[i-1][v];//当前物品重量大于剩余重量时，不放入 
    			else f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);//在放入和不放入两种情况选择最大的 
    		}
    	}
    	cout<<f[n][m]<<endl;
    	return 0;
    }

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No

发表评论取消回复

表情：

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

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

相关阅读

相关 01背包问题

[0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述： 0-1背包问题：给定

﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 257 阅读

相关 01背包问题

1.题目有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大，要求是：物品只能放一次。 2.分

系统管理员/ 2022年09月10日 11:27/ 0 赞/ 220 阅读

相关背包问题-背包01-苹果

package 动态规划.背包01; import java.util.Scanner; public class 苹果 \{ static class

野性酷女/ 2022年07月12日 12:12/ 0 赞/ 259 阅读

相关 01背包问题

![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54

╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 238 阅读

相关 01背包问题

public class package0_1 { int V[][] = new int[200][200];//物品选取，背包承重 int max(

约定不等于承诺〃/ 2022年06月08日 06:15/ 0 赞/ 244 阅读

相关 01背包问题

【例9.11】01背包问题时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】一个旅行者有一个最多能装M公斤的背包，现在有n件物

淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 240 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读

相关 01背包问题

简单背包问题设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S

痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 237 阅读

相关 01背包问题

转载：[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp73

怼烎@/ 2022年05月06日 15:00/ 0 赞/ 292 阅读

相关背包问题01

题目有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特

左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 329 阅读