【POJ】Charm Bracelet （01背包、贪心）

本文主要是介绍【POJ】Charm Bracelet （01背包、贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目大意：

有一个容量为M的背包和N(1 ≤ N ≤ 3,402) 件物品；对于第i件物品的重量是Wi (1 ≤ Wi ≤ 400)，而且它的价值是Di (1 ≤ Di ≤ 100)。现在将这N件中的其中几件物品装入背包使装入物品的总重量不超过背包容量M (1 ≤ M ≤ 12,880)，同时使这些物品总价值最大，最后输出这个价值。

AC：

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
const int N = 1234567;
int w[N], d[N], f[N];
int main()
{int n,m;	cin >> n >> m;for(int i=1;i<=n;i++)cin >> w[i] >> d[i];memset(f,0,sizeof(f));for(int j=1;j<=n;j++){for(int i=m;i>=0;i--){if(i>=w[j])f[i]=max(f[i],f[i-w[j]]+d[j]);}}cout << f[m] << endl;return 0;
}

 

这篇关于【POJ】Charm Bracelet （01背包、贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---