题目
题解思路
参考完全背包 超详细 讲解视频
状态方程 不同于01背包
当我们求最小值时 将第零列初始为0其他初始为最大值 ,每次取最小值。最大时,其他初始化为0,每次取最大即可。
完全背包可以进行 空间优化 。因为 更新的时候要么就是从上边要么从之前小容量的值。
这样就可以将二维降为一维!
if ( k < z[i] )
dp[k] = dp[k];
else
dp[k] = min( dp[k] , dp[k -z[i]] + j[i] );
AC代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
#define INF 106110956
#define IOS ios::sync_with_stdio(false);
int dp[10010];
int j[550];
int z[550];
int main ()
{
IOS
int t;
cin>>t;
while(t--)
{
int s,s1,n;
cin>>s>>s1>>n;
s = s1 -s;
for (int i = 1 ;i <= n ; i++ )
{
cin>>j[i]>>z[i];
}
for (int k = 1 ;k <= 10010 ; k++ ) //容量
{
dp[k] = INF ;
}
dp[0] = 0;
/* for (int i = 0 ; i <= n ; i++ ) //物品数
{
for (int k = 0 ;k <= s ; k++ ) //容量
{
cout<<dp[i][k]<<" ";
}
cout<<"\n";
} */
for (int i = 1 ; i <= n ; i++ ) //物品数
for (int k = 1 ;k <= s ; k++ ) //容量
{
if ( k < z[i] )
dp[k] = dp[k];
else
dp[k] = min( dp[k] , dp[k -z[i]] + j[i] );
} /*
for (int i = 0 ; i <= n ; i++ ) //物品数
{
for (int k = 0 ;k <= s ; k++ ) //容量
{
cout<<dp[i][k]<<" ";
}
cout<<"\n";
} */
if (dp[s] != INF )
cout<<"The minimum amount of money in the piggy-bank is "<<dp[s]<<"."<<endl;
else
cout<<"This is impossible."<<endl;
}
return 0;
}