初始化
恰好装满最优解：dp[0] = 0 , dp[i] = -oo （1<=i<=n）
没有要求最优解：dp[i] = 0
基础代码
dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])
空间优化
版本一
for (int i = 1; i <= n; i++)
for (int j = V; j >= 0; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
版本二
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
常数优化
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i], s[i] = s[i - 1] + w[i];
for (int i = 1; i <= n; i++) {
int bound = max(w[i], V - (s[n] - s[i]));
for (int j = V; j >= bound; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
#define lc id<<1
#define rc id<<1|1
#define test(x) cout<<"TEST "<<x<<endl;
const int mxn = 1e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 998244353 ;
using namespace std;
#define open freopen("input.in","r",stdin);freopen("output.in","w",stdout);
typedef long long ll;
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
int p,t,n,m,k,si,res,cnt,lg,ans;
int w[mxn] , v[mxn] , d[mxn] , s[mxn] , dp[mxn] ;
void solve()
{
rd(n) , rd(m) ; s[0] = 0 ;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
rd(w[i]) , rd(d[i]) ;
s[i] = s[i-1] + w[i] ;
}
for(int i=1;i<=n;i++){
int lim = max( w[i] , m - s[n] + s[i] );
for(int j=m;j>=lim;j--){
dp[j] = max(dp[j] , dp[j-w[i]] + d[i]) ;
}
}
printf("%d\n",dp[m]);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
const int mxn = 1e5+7;
int n,m,k,t,cnt,ans,lim,res,ok,num;
int c[mxn] , w[mxn] , dp[mxn] , s[mxn] ;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for(cin>>t;t;t--){
cin>>n>>lim;
memset(dp,0,sizeof(dp));
s[0] = 0 ;
for(int i=1;i<=n;i++) cin>>w[i] , s[i] = s[i-1] + w[i] ;
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<=n;i++){
int W = max(c[i] , lim - s[n] + s[i]);
for(int j=lim;j>=W;j--)
dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
}
cout<<dp[lim]<<endl;
}
}
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
const int mxn = 1e5+7;
int n,m,k,t,cnt,ans,lim,res,ok,num;
int cost[mxn] , w[mxn] , dp[mxn] ;
int main()
{
while(cin>>n&&n)
{
for(int i=1;i<=n;i++) cin>>cost[i];
sort(cost+1,cost+1+n);
memset(dp,0,sizeof(dp));
cin>>lim;
if(lim<5) {cout<<lim<<endl;continue;}
lim-=5;
for(int i=1;i<n;i++)
{
for(int j=lim;j>=cost[i];j--)
dp[j] = max(dp[j],dp[ j-cost[i] ]+cost[i]);
}
cout<<lim+5 - dp[lim]-cost[n]<<endl;
}
}
CD 【路径】
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
const int mxn = 1e5+7;
int n,m,k,t,cnt,ans,lim,res,ok,num;
int cost[mxn] , w[mxn] , dp[mxn] , pre[25][mxn] ;
int main()
{
while(cin>>lim)
{
cin>>n;
memset(dp,0,sizeof(dp));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++) cin>>cost[i];
for(int i=n;i;i--)
{
for(int j=lim;j>=cost[i];j--)
{
if(dp[j]<dp[ j-cost[i] ]+cost[i])
{
dp[j] = dp[ j-cost[i] ]+cost[i] ;
pre[i][j] = 1;
}
}
}
for(int i=1,j=lim;i<=n;i++)
if(pre[i][j]==1)
cout<<cost[i]<<" " , j-=cost[i] ;
cout<<"sum:"<<dp[lim]<<endl;
}
}
Dividing coins UVA - 562
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
const int mxn = 1e5+7;
int n,m,k,t,cnt,ans,lim,res,ok,num;
int cost[mxn] , w[mxn] , dp[mxn] , pre[25][mxn] ;
int main()
{
cin>>t;
while(t--)
{
cin>>n; ans=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) cin>>cost[i] , ans+=cost[i];
lim=ans/2;
for(int i=1;i<=n;i++)
{
for(int j=lim;j>=cost[i];j--)
{
if(dp[j]<dp[ j-cost[i] ]+cost[i])
{
dp[j] = dp[ j-cost[i] ]+cost[i] ;
}
}
}
cout<<abs( ans-2*dp[lim] )<<endl;
}
}
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
const int mxn = 1e4+7;
int n,m,k,t,cnt,ans,lim,res,ok,num;
int w[mxn] ;
double dp[mxn] , cost[mxn] ;
int main()
{
cin>>t;
while(t--)
{
double p; lim=0; n = 0 ;
memset(dp,0,sizeof(dp));
cin>>p>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>cost[i] , lim+=w[i] , cost[i]=1-cost[i];
dp[0] = 1.0 ;
for(int i=1;i<=n;i++)
{
for(int j=lim;j>=w[i];j--)
{
dp[j] = max( dp[j] , dp[j-w[i]]*cost[i] );
}
}
for(int i=lim;i>=0;i--)
{
if(dp[i]>=(1.0-p))
{
cout<<i<<endl;
break;
}
}
}
}
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
#define tle ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int inf = 1<<30;
const int mxn = 2e5+7;
int n,m,k,t,cnt,ans,lim,res,ok,num;
int dp[mxn] , cost[mxn] ,w[mxn] ;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>cost[i]>>w[i];
for(int i=0;i<=200000;i++) dp[i] = -inf;
dp[100000] = 0 ;
for(int i=1;i<=n;i++)
{
if(cost[i]<0 && w[i]<0) continue;
if(cost[i]>0)
{
for(int j=200000;j>=cost[i];j--)
if(dp[j-cost[i]] > -inf)
dp[j] =max( dp[ j-cost[i] ]+w[i] , dp[j] );
}
else
{
for(int j=cost[i];j<=200000+cost[i];j++)
if(dp[j-cost[i]] > -inf)
dp[j] =max( dp[ j-cost[i] ]+w[i] , dp[j] );
}
}
ans = -inf ;
for(int i=100000;i<=200000;i++)
if(dp[i]>=0)
ans = max(ans,dp[i]+i-100000);
cout<<ans<<endl;
}
/// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
#define tle ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int inf = 1<<30;
const int mxn = 2e5+7;
int n,m,k,t,v,cnt,ans,lim,res,ok,num;
int dp[mxn][32] , cost[mxn] , w[mxn] , mx1[31] , mx2[31];
int main()
{
for(cin>>t;t;t--)
{
cin>>n>>v>>k;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) cin>>cost[i];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=v;j>=cost[i];j--)
{
for(int _=1;_<=k;_++)
{
mx1[_] = dp[j][_];
mx2[_] = dp[j-cost[i]][_] + w[i] ;
}
mx1[k+1] = mx2[k+1] = -1 ;
int l = 1 , r = 1 , _ = 1 ;
while(_!=k+1 && (mx1[l]!=-1 || mx2[r]!=-1))
{
if(mx1[l]>mx2[r])
dp[j][_] = mx1[l++] ;
else
dp[j][_] = mx2[r++] ;
if(dp[j][_]!=dp[j][_-1]) _++;
}
}
}
cout<<dp[v][k]<<endl;
}
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
#define N 510
#define met(a, b) memset(a, b, sizeof(a))
int dp[N*10], n, m;
struct node
{
int v, q, p, qp;
}a[N];
int cmp(node p, node q)
{
return p.qp<q.qp;
}
int main()
{
while(scanf("%d %d", &n, &m)!=EOF)
{
met(a, 0);
met(dp, 0);
for(int i=1; i<=n; i++)
{
scanf("%d%d%d", &a[i].p, &a[i].q, &a[i].v);
a[i].qp = a[i].q - a[i].p;
}
sort(a+1, a+n+1, cmp);
for(int i=1; i<=n; i++)
{
for(int j=m; j>=a[i].q; j--)///dp[j]表示剩余j元钱所能购买物品的最大价值；
dp[j] = max(dp[j], dp[j-a[i].p]+a[i].v);
}
printf("%d\n", dp[m]);
}
return 0;
}
/// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
#define tle ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int inf = 1<<30;
const int mxn = 2e5+7;
int n,m,k,t,v,cnt,ans,lim,res,ok,num;
int dp[mxn][2] , cost[mxn] , w[mxn] , mx1[31] , mx2[31];
int main()
{
for(cin>>t;t;t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>cost[i];
for(int i=0;i<=m;i++)
dp[i][0] = 0 , dp[i][1] = 1 ;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=cost[i];j--)
{
if(dp[j][0]==dp[ j-cost[i] ][0]+1)
dp[j][1] = dp[j-cost[i]][1] + dp[j][1] ;
else if(dp[j][0] < dp[j-cost[i]][0]+1)
dp[j][0] = dp[j-cost[i]][0]+1 ,
dp[j][1] = dp[j-cost[i]][1] ;
}
}
if(dp[m][0])
cout<<"You have "<<dp[m][1]<<" selection(s) to buy with "<<dp[m][0]<<" kind(s) of souvenirs."<<endl;
else
cout<<"Sorry, you can't buy anything."<<endl;
}
}
