【HDU1114】完全背包

1.​​題目連結​​。題目說了很多，但是意思就是給你一個儲蓄罐，空着的時候的重量和最多能夠承受的重量，然後給你一些硬币，這些硬币有價值和重量，找出把這個儲蓄罐裝滿的時候硬币加起來最小的值。

2.這很類似01背包的問題，但是也有差別。我們知道在01背包中每個物品隻有一個，但是這裡的硬币（物品）無限多。我們把這種問題叫做完全背包。

3.完全背包我們需要考慮的問題不再是這種物品拿與不拿，而是拿幾個的問題。是以DP方程很好寫：

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
#define inf (1<<20)
const int n = 1e5 + 10;
int dp[n], w[n], v[n];
int main()
{
  int T;
  int E, F;
  int W;
  scanf("%d", &T);
  int N;
  while (T--)
  {
    scanf("%d%d", &E, &F);
    W = F - E;//容量
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
      scanf("%d%d", &v[i], &w[i]);
    }
    for (int i = 0; i <= W; i++)
    {
      dp[i] = inf;
    }
    dp[0] = 0;
    for (int i = 0; i < N; i++)
    {
      for (int j = w[i]; j <= W; j++)
      {
        dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
      }
    }
    if (dp[W]<inf)
    {
      printf("The minimum amount of money in the piggy-bank is %d.\n", dp[W]);
    }
    else
    {
      printf("This is impossible.\n");

    }
  }
  return 0;
}