01 背包问题 (价值)
例题 https://www.luogu.org/problemnew/show/P1048 最基本的背包, 没有拐弯
注意点:
二维 dp 数组是 dp[i+1][w+1], 后面那个千万别开小了
背包大小为 0, 或者物品大小为 0 时, 价值全部为 0. 因此两个 for 全部初始化为 0!
还原最优解物品组合要标记
- cin>>W>>N;
- FOR(i,1,N)
- {
- cin>>a[i].wei>>a[i].val;
- }
- FOR(i,1,N)
- {
- dp[i][0]=0;
- }
- FOR(i,1,W)
- {
- dp[0][i]=0;
- }
- FOR(i,1,N)
- FOR(j,1,W)
- {
- /*if(a[i].wei>j)
- {
- dp[i][j]=dp[i-1][j];
- }
- else
- {
- dp[i][j]=max(dp[i-1][j-a[i].wei]+a[i].val,dp[i-1][j]);
- }*/
- dp[i][j] = dp[i-1][j];
- if(a[i].wei>j)
- continue;
- if(a[i].val+dp[i-1][j-a[i].wei]>dp[i-1][j])
- dp[i][j] = a[i].val+dp[i-1][j-a[i].wei];
- }
- cout<<dp[N][W];
- 3:for(int i=N,w=W;i>=1;i--)
- {
- if(G[i][w]==diagonal)
- {
- cout<<i<<endl;
- w-=a[i].wei;
- }
- }
补充另一个背包问题, 填充型背包
https://www.luogu.org/problemnew/show/P1049 没拐弯
- cin>>M>>N;
- FOR(i,1,N)
- {
- cin>>v[i];
- }
- for(int i=1;i<=N;++i)
- for(int j=M;j>=v[i];--j)
- {
- f[j]=max(f[j],f[j-v[i]]+v[i]);
- }
- cout<<M-f[M];
来源: http://www.bubuko.com/infodetail-2945235.html