虽然说这题多重背包很明显,但是没有花一点时间是过不了的,TLE 了n次啊,一开始直接用 多重背包 做法直接上,结果T了,后来也看了一些别人的做法,真的是需要思考啊。。
因为这题是判断最后 是否 符合条件,因此没必要 记录 最优结果,因此只要 利用 bool (int就 TLE,各种yy)记录是否 满足条件就可以了。
在 01 背包中,dp[i]=dp[i]|dp[i-cost],表示i的状态要么由 本身 或者 i-cost 推过来,本来是 dp[i]=max(dp[i],dp[i-cost]+weight),但是这边没必要了。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxV=100005;
const int maxn=105;
int c[maxn],w[maxn];
int n,V;
bool dp[maxV];
void ZeroOnePack(int cost){
for(int i=V;i>=cost;i--)dp[i]|=dp[i-cost];
}
void CompletePack(int cost){
for(int i=cost;i<=V;i++)dp[i]|=dp[i-cost];
}
void MultiplePack(int cost,int amount){
if(cost*amount>=V)CompletePack(cost);
else {
int k=1;
while(k<amount){
ZeroOnePack(k*cost);
amount-=k;
k<<=1;
}
ZeroOnePack(amount*cost);
}
}
int main(){
while(scanf("%d%d",&n,&V)&&(n||V)){
for(int i=1;i<=n;i++)scanf("%d",w+i);
for(int i=1;i<=n;i++)scanf("%d",c+i);
//memset(dp,0,sizeof(dp));
for(int i=0;i<=V;i++)dp[i]=0;
dp[0]=1;
for(int i=1;i<=n;i++){
if(c[i])MultiplePack(w[i],c[i]);
}
int ans=0;
for(int i=1;i<=V;i++)if(dp[i])ans++;
printf("%d\n",ans);
}
return 0;
}
更多详细信息请查看
java教程网 http://www.itchm.com/forum-59-1.html
分享到:
相关推荐
晒代码之二——多重背包(POJ1276)
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
北大POJ2002-Squares 解题报告+AC代码
poj 百练 题目分类 poj 百练 题目分类