CSUOJ动态规划简单题型

题目：
Description
Potato sacks come in different weight capacities (specified in pounds). Potatoes come in different weights. If you are given some number of potatoes of possibly different weights (specified in pounds), determine if it is possible to exactly fill a potato sack of a given capacity using some or all of the potatoes.

Input
The first line of input contains a single decimal integer P,(1 ≤ P ≤ 100), which is the number of data sets that follow. Each data set should be processed identically and independently. Each data set consists of a single line of input containing 12 space separated positive integers. They are the data set number, K, followed by the capacity, C, of the potato sack in pounds, 10 ≤ C ≤ 30, followed by the weights of 10 potatoes in pounds. A potato will not weigh more than 3 pounds.

Output
For each data set there is a single line of output. The output line consists of the data set number,K, followed by a single space, the word YES if the potato sack can be filled exactly to capacity C pounds or the word NO if it cannot be filled exactly

Sample Input
2
1 20 3 2 1 3 3 2 3 2 1 1
2 25 3 3 3 3 3 3 3 3 3 3
Sample Output
1 YES
2 NO

思路：可以看得出是一道01背包问题，比01背包更简单的背包，也就是每个背包的价值都默认为1。
1、开一个dp[i][j] 二位数组来表示在放前i个土豆时不超过j这个容积所能放入的最大的总体积。

for(int i = 0 ; i< 10 i++){for(int j = a[i]; j<=vtotal; j++){//              不放        放dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i]] + a[i]);}
}

2、开一个dp[i]一维数组来表示在容积为j时所能放入的最大总体积。

for(int i = 0;i<10; i++){for(int j = a[i]; j <= vtotal ; j++){    //从前往后遍历dp[j] = max(dp[j],dp[j-v[i]]+v[i]);}
}
for(int i = 0;i<10; i++){for(int j = vtotal; j >= a[i]; j--){    //从前往后遍历dp[j] = max(dp[j],dp[j-v[i]]+v[i]);}
}

AC代码;

#include
#include
#include
using namespace std;  //  p 100         Vtotal  30 
#define maxn 10050
int Vtotal;
int a[10];
int dp[maxn];   //dp[i]为不超过i时所放的最大质量数
int main(int argc, char const *argv[])
{int count,e,scount;cin>>count;scount = count;while(count--){cin>>e>>Vtotal;for (int i = 0; i < 10; ++i){cin>>a[i];}memset(dp,0,sizeof(dp));for (int i = 0; i < 10; ++i)  //遍历一遍是否有可以放入的{for (int j = a[i]; j <=Vtotal; j++)  //从左向右遍历{dp[j] = max(dp[j],dp[j-a[i]]+a[i]); }}if (dp[Vtotal] == Vtotal){cout<