300-求解0-1背包问题

古城微笑少年丶 2023-01-17 03:21 164阅读 0赞

**题目如下：**

> 状态：dp\[i\]\[j\]:背包为j的情况下，所选物品的范围是从i到n，背包的最大价值。  
> 状态转移：  
> 当i == n时候，如果w\[i\] > j dp\[i\]\[j\] =0; 如果:w\[i\]>=j dp\[i\]\[j\] = v\[i\]; … i；  
> 如果w\[i\]<j dp\[i\]\[j\] = dp\[i+1\]\[j\]  
> 如果w\[i\]>=j 选择这个物品和不选择这个物品的最大值： max\{dp\[i+1\]\[j\], v\[i\]+dp\[i+1\]\[j-w\[i\]\]\}

## 解题代码如下 ##

int OneZeroBag(vector<int>& w, vector<int>& v, int c)
    {
        
    	int n = w.size();
    	vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
    	for (int j = 1; j <= c; ++j)
    	{
        
    		if (w[n - 1] > j)
    		{
        
    			// 第n个物品的重量 大于 背包剩余容量
    			dp[n][j] = 0;
    		}
    		else
    		{
        
    			// 第n个物品的重量 小于等于 背包的剩余容量
    			dp[n][j] = v[n];
    		}
    	}
    	for (int i = n - 1; i >= 0; --i)
    	{
        
    		for (int j = 1; j <= c; ++j)
    		{
        
    			if (w[i - 1] > j)
    			{
        
    				// 第i个物品无法装入背包
    				dp[i][j] = dp[i + 1][j];
    			}
    			else
    			{
        
    				dp[i][j] = std::max(dp[i + 1][j], v[i - 1] + dp[i + 1][j - w[i - 1]]);
    			}
    		}
    	}
    	return dp[n][c];
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 POJ 3624 （01背包一维求解）

Charm Bracelet <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

左手的ㄟ右手/ 2024年02月17日 19:31/ 0 赞/ 117 阅读

相关 300-求解0-1背包问题

题目如下： > 状态：dp\[i\]\[j\]:背包为j的情况下，所选物品的范围是从i到n，背包的最大价值。 > 状态转移： > 当i == n时候，如果w\[i\]

古城微笑少年丶/ 2023年01月17日 03:21/ 0 赞/ 165 阅读

相关 01背包问题

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

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

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

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

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

相关 01背包问题

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

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

相关 01背包问题

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

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

相关 01背包问题

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

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

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

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

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

相关 01背包问题

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

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

相关背包问题01

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

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