HDU1114 Piggy

HDU1114 Piggy

题目：

传送门

题意：

给定🐖钱罐前后的重量，求出里面最少装多少钱。

分析：

必须满足是某重量，相当于必须装满。
所以本题是完全背包求最小价值。

下面是原来总结的：

1. 在恰好装满的情况下取最大值

dp全被初始化为最小值（-INF）
dp[0]=0;

如果dp[n]<0，则在容量为n时，背包无法装满。
恰好装满的dp[n]有一个具体值，而不是-INF

2.在恰好装满的情况下取最小值

注意
INF的取值并不是越大越好，INF过大会有溢出问题，一般在int32位整数数据时INF取0x3f3f3f3f

饿，copy完才发现自己wa到了2的注意里，还是没有注意。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e4+3;
int dp[maxn];
int  w[maxn],v[maxn];
int inf=1e6;
int main()
{int t;cin>>t;while(t--){for(int i=0;i<maxn;i++)dp[i]=inf;int w1,w2;scanf("%d%d",&w1,&w2);int n; scanf("%d",&n);int V=w2-w1;dp[0]=0;for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);}for(int i=1;i<=n;i++)for(int j=v[i];j<=V;j++)//注意这里dp[j]=min(dp[j],dp[j-v[i]]+w[i]);if(dp[V]!=inf){printf("The minimum amount of money in the piggy-bank is %d.n",dp[V]);}else  printf("This is impossible.n");}return 0;
}