【动态规划】背包问题相关题目

1.poj 1742

Description

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4

题解：

　　可以看出问题属于背包问题，且每件物品选取次数有限制，故为多重背包问题。而且此题没有涉及到最大价值问题，为之前讲的多重背包的变体。令dp[i+1][j]为取前i种硬币加和为j后第i种硬币最多剩余数，则dp[i][j] >= 0说明price = j可以达到，否则就是无法达到。

Solution 1

#include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <algorithm>
using namespace std;

int dp[100000 + 5];
int w[100 + 5], v[100 + 5];
int n, m;

int main(){
  int i, j ,res;
  while(scanf("%d%d", &n, &m) != EOF && (m || n)){
      for(i = 0; i < n; ++i){
        scanf("%d", &w[i]);
      }
      for(i = 0; i < n; ++i){
        scanf("%d", &v[i]);
      }
      memset(dp, -1, sizeof(dp));
      dp[0] = 0;
      for(i = 0; i < n; ++i){
          for(j = 0; j <= m; ++j){
            if(dp[j] >= 0) {
              dp[j] = v[i];
            }
            else if(j < w[i] || dp[j - w[i]] <= 0){
              dp[j] = -1;
            } else {
              dp[j] = dp[j - w[i]] - 1;
            }
          }
      }
      res = 0;
      for(i = 1; i <= m; ++i){
        if(dp[i] >= 0)
          ++res;
      }
      printf("%d
", res);
  }
  return 0;
}

Solution 2

#include <cstdio>  
#include <cstring>  
#include <iostream>  

using namespace std;
int dp[100000 + 5], used[100000 + 5];
int w[100 + 5], v[100 + 5];
int n, m;

int main(){
  int res;
  while(scanf("%d%d", &n, &m) != EOF && (m || n)){
      for(int i = 0; i < n; ++i){
        scanf("%d", &w[i]);
      }
      for(int i = 0; i < n; ++i){
        scanf("%d", &v[i]);
      }
      memset(dp, 0, sizeof(dp));
      dp[0] = 1;
      res = 0;
      for(int i = 0; i < n; ++i){
          memset(used, 0, sizeof(used));
          for(int j = w[i]; j <= m; ++j){
            if(!dp[j] && dp[j - w[i]] && used[j - w[i]] < v[i]){
              dp[j] = 1;
              used[j] = used[j - w[i]] + 1;
              ++res;
            }
          }
      }
      printf("%d
", res);
  }
  return 0;
}

　　其中dp[j]表示能否加和为j。used[j]表示最少要用多少个w[i]能加和达到j。

　　从此题可知，多重背包模板还可以为

dp初始化，因题而异
for(int i = 0; i < n; ++i){
    memset(used, 0, sizeof(used));
    for(int j = w[i]; j <= MAX_M; ++j){
        if(!dp[j] && dp[j - w[i] && used[j - w[i]] < v[i]){
            ...对dp的操作及其他操作，因题而异
            used[j] = used[j - w[i]] + 1;//想要达到j最少使用w[i]的个数。
        }
    }
}