【转】http://blog.csdn.net/zxy_snow/article/details/6003790
一维:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
int bag[12900];
int w[3410],v[3410];
int main(void)
{
int n,m;
cin >> n >> m;
for(int i=1; i<=n; i++)
cin >> w[i] >> v[i];
memset(bag,0,sizeof(bag));
for(int i=1; i<=n; i++)
for(int k=m; k>=w[i]; k--)
if( bag[k-w[i]]+ v[i] > bag[k] )
bag[k] = bag[k-w[i]]+ v[i];
cout << bag[m] << endl;
return 0;
}
二维:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
int bag[100][100];
int w[3410],v[3410];
int main(void)
{
int n,m;
cin >> n >> m;
for(int i=1; i<=n; i++)
cin >> w[i] >> v[i];
memset(bag,0,sizeof(bag));
for(int i=1; i<=n; i++)
for(int k=1; k<=m; k++)
if( k >= w[i])
{
if( bag[i-1][k-w[i]]+ v[i] > bag[i-1][k] )
bag[i][k] = bag[i-1][k-w[i]]+ v[i];
else
bag[i][k] = bag[i-1][k];
}
else
bag[i][k] = bag[i-1][k];
cout << bag[n][m] << endl;
return 0;
}
分享到:
相关推荐
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
POJ水题集-----50道左右-----增加自信啊..
西北工业大学-c语言-POJ-题目及答案-第七季.doc
用Java代码实现POJ(PKU)上题2494!
很有用的解题报告。。是acm初级提高的必备资料。。。。。
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
poj 1028 Web Navigation 的代码,已通过!
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
北大POJ2002-Squares 解题报告+AC代码
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
NULL 博文链接:https://128kj.iteye.com/blog/1752661
POJ3211--Washing Clothes
NULL 博文链接:https://128kj.iteye.com/blog/1754177