【转】http://blog.csdn.net/zxy_snow/article/details/6052676
这个相当于体积和价值一样大的01背包。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <limits.h>
using namespace std;
int w[1000002],bag[20000005];
int main(void)
{
int n,c;
while( scanf("%d %d",&n,&c)!=EOF )
{
int sum = 0;
for(int i=1; i<=n; i++)
{
scanf("%d",&w[i]);
sum += w[i];
}
for(int i=1; i<=c; i++)
bag[i] = 0;
for(int i=1; i<=n; i++)
for(int k=sum; k>=w[i]; k--)
{
if( bag[k] < bag[k-w[i]] + w[i] )
bag[k] = bag[k-w[i]] + w[i];
}
int min = INT_MAX;
for(int i=c; i<=sum; i++)
{
if( bag[i] >= c && bag[i] - c < min )
min = bag[i] - c;
}
cout << min << endl;
}
return 0;
}
分享到:
相关推荐
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1690 Your-Term-Project.md
POJ水题集-----50道左右-----增加自信啊..
poj 1240 Pre-Post-erous!.md
西北工业大学-c语言-POJ-题目及答案-第七季.doc
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
用Java代码实现POJ(PKU)上题2494!
很有用的解题报告。。是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
POJ3211--Washing Clothes
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
NULL 博文链接:https://128kj.iteye.com/blog/1752661
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类