首页 > 代码库 > POJ3624(背包问题)
POJ3624(背包问题)
1、题目链接地址
http://poj.org/problem?id=3624
2、源代码
#include<iostream>using namespace std;#define MAXN 3403 //物品的最大数量#define MAXM 12881 //重量的上限 int max(int x, int y){ if (x > y) return x; else return y;} int main(){ int n, m; //n:个数,m:不能超过的重量 while(cin >> n >> m && n && m) { int i, v; int w[MAXN] = {0}; //重量 int d[MAXN] = {0}; //需要程度 int dp[MAXM] = {0}; for (i = 1; i <= n; i++) cin >> w[i] >> d[i]; for (i = 1; i <= n; i++)//重点位置 { for (v = m; v >= w[i]; v--) dp[v] = max(dp[v], dp[v - w[i]] + d[i]); } cout << dp[m] << endl; } return 0;}
3、分析
这个题的背包的承重量为m,物品的个数为n,物品的重量w[],物品的需要程度d[],dp[]辅助数组.
以上面的数据为例
4 6 //物品的个数为4, 背包的称重量为6
1 4 //重量为1,需要程度4
2 6 //重量为2,需要程度6
3 12 //重量为3,需要程度12
2 7 //重量为2,需要程度7
对于第一物品的作出决定的时候
i = 1, v = 6, dp[6] = max(dp[6], dp[5] + d[1]) = max(0, 0 + 4) = 4;
i = 1, v = 5, dp[5] = max(dp[5], dp[5 - w[1] + d[1]) = max(0,dp[4] +4) = 4;
一直算,有如下的结果:
i\v | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 4 | 4 | 4 | 4 | 4 | 4 |
2 | 4 | 6 | 10 | 10 | 10 | 10 |
3 | 4 | 6 | 12 | 16 | 18 | 22 |
4 | 4 | 7 | 12 | 16 | 19 | 23 |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。