UVA11137 Ingenuous Cubrency 完全背包 递推式子

时间:2022-09-11 15:03:38

做数论都做傻了,这道题目 有推荐,当时的分类放在了递推里面,然后我就不停的去推啊推啊,后来推出来了,可是小一点的数 输出答案都没问题,大一点的数 输出答案就是错的,实在是不知道为什么,后来又不停的看,突然有股傻眼的感觉,这个貌似很面善很面熟啊,不禁想起以前一到背包题目,也是给了具体数字 最大范围,最后使用背包来解决的,那么这道有些相似,后来翻了 背包九讲的PDF,我了个去,这不就是 完全背包么?

恨死!!!一定要牢牢记住!!!

有N种物品和一个容量为V的背包,每种物品都有无限件可用。
第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大!!!  
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set> #define ll long long
#define LL __int64
#define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;
//
//vector<int>G[30012]; ll d[10002]; void init()
{
memset(d,0,sizeof(d));
d[0]=1;
for(ll i=1;i<=21;i++)
for(ll j=i*i*i;j<=10002;j++)
d[j]+=d[j-i*i*i];
} int main(void)
{
init();
ll n;
while(cin>>n)
{
cout<<d[n]<<endl;
}
}