本文主要是介绍poj1742 dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题：http://poj.org/problem?id=1742
和之前那一篇hdu2844是一道题，但是这一题的数据量，用O（V*log2（Mi））的多重背包二进制拆分是超时的，为了缩短时间，必须更改dp数组的定义和状态转移方程
定义f[i][j]表示的是前i种硬币用来拼价值j，拼成后第i种硬币剩余的数量。
有j<w[i]，代表第i件物品1件都比价值j大，所以第i件物品没法用，f[i][j]=-1
有f[i][j-w[i]]<=0 如果用第i件物品拼成j-w[i]正好拼成（第i件物品正好用完）或者 拼不成(<0)，那更不可能拼成价值j的物品
else
f[i]j[=f[i][j-w[i]]-1;
初始化
f全为-1，然后f[0][0]=0; 然后3重for循环从第一件开始推。
注意：上述还需要优化，否则超内存！二维-》一维数组 f[j] j是要拼的价值 然后i，j从小到大循环，保证这一层可以用上一层的值推出。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define max(a,b)(a>b?a:b)
int w[103];
int num[103];
int f[100005];
int n,m;
int main()
{
while(~scanf("%d%d",&n,&m)&&n&&m)
{
int i,j;
memset(f,-1,sizeof(f));
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
f[0]=0;
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
{
if(f[j]>=0)
f[j]=num[i];
else if(j<w[i]||f[j-w[i]]<0)
f[j]=-1;
else
f[j]=f[j-w[i]]-1;
}
int sum=0;
for(i=1;i<=m;i++)
if(f[i]>=0)
sum++;
printf("%d\n",sum);
}
}
这篇关于poj1742 dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
